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 <= 30pre[] 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; }}