106 从中序与后序遍历序列构造二叉树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTreeHelper(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1);
    }

    private TreeNode buildTreeHelper(int[] inorder, int i_start, int i_end, int[] postorder, int p_start, int p_end) {
        if (i_start > i_end)
            return null;
        
        int rootVal = postorder[p_end];
        int index = 0;
        for (int i = i_start; i <= i_end; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        int leftSize = index - i_start;
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTreeHelper(inorder, i_start, index-1, postorder, p_start, p_start+leftSize-1);
        root.right = buildTreeHelper(inorder, index+1, i_end, postorder, p_start+leftSize, p_end-1);
        return root;
    }