题目

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

思路

跟之前前中序构建二叉树一样，不过是根据后序的最后一个来判断root节点

代码

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        TreeNode root = null;
        if (postorder.length == 0 || inorder.length == 0) {
            return root;
        }
        root = new TreeNode(postorder[postorder.length-1]);
        int tmp = 0;
        for (int i = 0; i < inorder.length; i++) {
            tmp = i;
            if(root.val == inorder[i]){
                break;
            }
        }
        int[] leftInorder = Arrays.copyOfRange(inorder,0,tmp);
        int[] rightInorder = Arrays.copyOfRange(inorder,tmp+1,inorder.length);
        int[] leftPostorder = Arrays.copyOfRange(postorder,0,tmp);
        int[] rightPostorder = Arrays.copyOfRange(postorder,tmp,postorder.length-1);
        root.left = buildTree(leftInorder,leftPostorder);
        root.right = buildTree(rightInorder,rightPostorder);
        return root;
    }