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[]
andpost[]
are both permutations of1, 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 }
相关题目
105. Construct Binary Tree from Preorder and Inorder Traversal
106. Construct Binary Tree from Inorder and Postorder Traversal
889. Construct Binary Tree from Preorder and Postorder Traversal