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.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
return dfs(pre, 0, pre.length - 1, post, 0, pre.length - 1);
}
private TreeNode dfs(int[] pre, int preStart, int preEnd, int[] post, int postStart, int postEnd){
if(preStart > preEnd){
return null;
}
TreeNode root = new TreeNode(pre[preStart]);
// 已经遍历完成的，直接返回最后一个节点
if (preStart == preEnd) {
return root;
}
// post节点从初始位置开始数，直到当前节点等于 前序遍历当前节点的下一个节点，因为下一节点为左右节点分割线
int postIndex = postStart;
while(post[postIndex] != pre[preStart + 1]){
postIndex++;
}
// 获取左侧节点的长度
int len = postIndex - postStart + 1;
// 左侧节点的pre为 start+1往后数len个长度；post节点为start开始往后到postIndex
root.left = dfs(pre, preStart+1, preStart+len, post, postStart, postStart+len);
// 右侧节点的pre为从preStart+len+1开始一直到结束preEnd；post节点为postStart+len开始到去掉最后的根结点
root.right = dfs(pre, preStart+len+1, preEnd, post, postStart+len, postEnd - 1);
// 注意pre都+1是因为第一个节点为根结点，要去掉
return root;
}
}