106. Construct Binary Tree from Inorder and Postorder Traversal

Link

Solution

同105

class Solution {
    public int postorderIndex = 0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postorderIndex = postorder.length -1;
        TreeNode root = dfs(inorder, postorder, 0, inorder.length-1);
        return root;
    }
    
    public TreeNode dfs(int[] inorder, int[] postorder, int inorderStart, int inorderEnd){
        if(postorderIndex < 0) return null;
        
        TreeNode node = new TreeNode(postorder[postorderIndex]);
        int index = -1;
        for(int i = inorderStart; i <= inorderEnd; i++){
            if(inorder[i] == postorder[postorderIndex]){
                index = i;
                break;
            }
        }
        if(index != inorderEnd){
            postorderIndex--;
            node.right = dfs(inorder, postorder, index+1, inorderEnd);
        }
        
        if(index != inorderStart){
            postorderIndex--;
            node.left = dfs(inorder, postorder, inorderStart, index-1);
        }
        return node;
        
    }