[LeetCode] 889. Construct Binary Tree from Preorder and Postorder Traversal

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

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

返回与给定的前序和后序遍历匹配的任何二叉树。

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 的排列
每个输入保证至少有一个答案。如果有多个答案，可以返回其中一个。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题跟105，106题类似，也是给你X序遍历的结果，请你返回原生的树。这道题给的是前序遍历和后序遍历，这里有几个特点需要强调

前序遍历的第一个节点/后序遍历的最后一个节点是根节点
在前序遍历中，节点的排列差不多是类似这样，[root, root.left......, root.right......]
在后序遍历中，节点的排列差不多是类似这样，[root.left......, root.right......, root]

在前序遍历中，由于第一个节点是根节点，所以第二个节点一定来自于左子树，而且他是直接连接到根节点的左孩子。又因为后序遍历中如果根节点是有左孩子的话，这个左孩子 root.left 会在后序遍历中左子树节点的最后一个被遍历到。我们依据这个信息来把左右子树分割开来。

这里我们利用一个hashmap，记录后序遍历<节点，节点在postorder中的index>，这样当我们找到例子中的节点2的时候，我们就知道了在后序遍历中从开头到2的这一段是左子树的节点；2之后到post.length - 2这一段是右子树的节点。

时间O(n)

空间O(n)

Java实现

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode() {}
 8  *     TreeNode(int val) { this.val = val; }
 9  *     TreeNode(int val, TreeNode left, TreeNode right) {
10  *         this.val = val;
11  *         this.left = left;
12  *         this.right = right;
13  *     }
14  * }
15  */
16 class Solution {
17     public TreeNode constructFromPrePost(int[] pre, int[] post) {
18         // <postorder里每个元素, 下标>
19         HashMap<Integer, Integer> map = new HashMap<>();
20         for (int i = 0; i < post.length; i++) {
21             map.put(post[i], i);
22         }
23         return helper(pre, 0, pre.length - 1, post, 0, post.length - 1, map);
24     }
25 
26     private TreeNode helper(int[] preorder, int preStart, int preEnd, int[] postorder, int poStart, int poEnd,
27             HashMap<Integer, Integer> map) {
28         if (preStart > preEnd || poStart > poEnd) {
29             return null;
30         }
31         TreeNode root = new TreeNode(preorder[preStart]);
32         if (preStart + 1 <= preEnd) {
33             // length of left subtree array
34             int index = map.get(preorder[preStart + 1]) - poStart;
35             root.left = helper(preorder, preStart + 1, preStart + 1 + index, postorder, poStart, poStart + index, map);
36             root.right = helper(preorder, preStart + 1 + index + 1, preEnd, postorder, poStart + index + 1, poEnd - 1,
37                     map);
38         }
39         return root;
40     }
41 }