题目
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.
讲解
先序遍历和后序遍历无法确定一颗二叉树，所以这里有可能返回多种不同的树，但只要是正确的就行。
解这道题的关键在于分割左右子树，先序遍历中紧跟根节点后的也有可能不是左子树，但如果是这样的话，后续遍历中也不会有左子树，那么右子树的根节点就会在两种遍历中都挨着总根节点。所以思路就出来了，我们在先序遍历中拿到根节点后面的那个节点，然后在后序遍历中找到这个节点，这个点就在后序遍历中分割出了左右子树。
递归之。
Java 代码
/**
* 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) {
return constructFromPrePost(pre, 0, pre.length-1, post, 0, post.length-1);
}
private TreeNode constructFromPrePost(int[] pre, int preLeft, int preRight, int[] post, int postLeft, int postRight){
if(preLeft>preRight || postLeft>postRight){
return null;
}else if(preLeft==preRight){
return new TreeNode(pre[preLeft]);
}
TreeNode root = new TreeNode(pre[preLeft]);
for(int i=postRight-1;i>=postLeft;i–){
if(post[i]==pre[preLeft+1]){
root.left = constructFromPrePost(pre, preLeft+1, preLeft+1+i-postLeft, post, postLeft, i);
root.right = constructFromPrePost(pre, preLeft+2+i-postLeft, preRight, post, i+1, postRight-1);
}
}
return root;
}
}