889. 根据前序和后序遍历构造二叉树

返回与给定的前序和后序遍历匹配的任何二叉树。
pre 和 post 遍历中的值是不同的正整数。
示例：
输入：pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
提示：1 <= pre.length == post.length <= 30
pre[] 和 post[] 都是 1, 2, ..., pre.length 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

思路

令左分支有 LL 个节点。我们知道左分支的头节点为 pre[1]，但它也出现在左分支的后序表示的最后。所以 pre[1] = post[L-1]（因为结点的值具有唯一性），因此 L = post.indexOf(pre[1]) + 1。
现在在我们的递归步骤中，左分支由 pre[1 : L+1] 和 post[0 : L] 重新分支，而右分支将由 pre[L+1 : N] 和 post[L : N-1] 重新分支。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre.length != post.length) {
            return null;
        } 
        
        return buildMyTree(pre, 0, pre.length-1, post, 0, post.length-1);
    }
    
    public TreeNode buildMyTree(int[] pre,
                                int preStart,
                                int preEnd,
                                int[] post,
                                int postStart,
                                int postEnd) {
        if (preStart == preEnd) {
            return new TreeNode(pre[preStart]);
        }
        if (preStart > preEnd) {
            return null;
        }
        if (postStart > postEnd) {
            return null;
        }
        
        int root_value = pre[preStart];
        TreeNode root = new TreeNode(root_value);
        int root_left_value = pre[preStart+1];
        int position = findPosition(post, postStart, postEnd, root_left_value);
        if (position == -1) {
            return null;
        }
        
        root.left = buildMyTree(pre, preStart+1, preStart+1+position-postStart, post, postStart, position);
        root.right = buildMyTree(pre, preStart+position-postStart+2, preEnd, post, position+1, postEnd-1);
        
        return root;
    }
    
    public int findPosition(int[] post, int start, int end, int key) {
        for (int i = start; i <= end; i++) {
            if (post[i] == key) {
                return i;
            }
        }
        return -1;
    }
}