[Leetcode] Construct Binary Tree from Inorder and Postorder Traversal

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

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

由于树中没有重复的值，那么我们可以通过从后序遍历中找到根节点，然后根据中序遍历中根的位置来确定左子树和右子树。

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        if(n == 0) return null;
        if(n == 1) return new TreeNode(inorder[0]);
        int key = postorder[n-1];
        int ind = 0;
        
        while(inorder[ind] != key) ind++;
        int[] il = new int[ind];
        int[] pl = new int[ind];
        int[] ir = new int[n-ind-1];
        int[] pr = new int[n-ind-1];
        for(int i = 0; i < ind; i++) {
            il[i] = inorder[i];
            pl[i] = postorder[i];
        }
        for(int i = 0; i < n-ind-1; i++) {
            ir[i] = inorder[ind+i+1];
            pr[i] = postorder[ind+i];
        }
        TreeNode root = new TreeNode(key);
        root.left = buildTree(il, pl);
        root.right = buildTree(ir, pr);
        return root;
    }