889. Construct Binary Tree from Preorder and Postorder Traversal

Created: 10/31/2021

Leetcode

Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]

Constraints:

• 1 <= preorder.length <= 30

• 1 <= preorder[i] <= preorder.length

• All the values of preorder are unique.

• postorder.length == preorder.length

• 1 <= postorder[i] <= postorder.length

• All the values of postorder are unique.

• It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.

Basic Idea:

首先我们可以注意到在preorder中每次都是root在最前面，而在postorder中root则会在最后面，利用这个性质我们可以递归地每次将左右子树所对应的array分离出来，然后递归调用求解。

例如对于上图中的例子

preorder:   [1,  2,4,5,  3,6,7], 
postorder = [4,5,2,  6,7,3,  1]

在第一层中，我们可以知道当前层对应的node为1，然后2一定是下一层subtree的root，然后在postorder
中找到2的为止，接下来我们就知道左子树对应的数组为[245]和[452], 右子树则是剩下的[367]和[673]。

那么如果没有左子树，只有右子树呢？这种情况下我们无法分辨唯一的子树是左边还是右边，可以只将其当作
左子树。

Java Code:

// 1 245 367
// 452 673 1
//   |
//  mid
class Solution {
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        return build(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
    }
    
    private TreeNode build(int[] pre, int[] post, int preStart, int preEnd, int postStart, int postEnd) {
        if (preStart > preEnd) return null;
        if (preStart == preEnd) return new TreeNode(pre[preStart]);
        TreeNode root = new TreeNode(pre[preStart]);
        int mid = postStart;
        while (post[mid] != pre[preStart + 1]) mid++;
        root.left = build(pre, post, preStart + 1, preStart + (mid - postStart) + 1, postStart, mid);
        root.right = build(pre, post, preStart + (mid - postStart) + 2, preEnd, mid + 1, postEnd - 1);
        return root;
    }
}