106. Construct Binary Tree from Inorder and Postorder Traversal 105. Construct Binary Tree from Preorder and Inorder Traversal 由前序遍历+中序遍历（或中序遍历+后序遍历）重建二叉树。
以前序+中序为例，前序为根左右，因此第一个出现的为根节点，而中序则是左根右，根节点位于中间。因此可以在中序遍历中找根节点的位置，此位置左边为左子树，右边都为右子树。如此分别递归左子树与右子树的序列，即能重建二叉树。 /** - Definition for a binary tree node. - public class TreeNode { - int val; - TreeNode left; - TreeNode right; - TreeNode(int x) { val = x; } - } */ public class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return helper(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } public TreeNode helper(int[] preorder,int startPre,int endPre,int[] inorder,int startIn,int endIn){ if(startPre>endPre || startIn>endIn) return null; TreeNode root = new TreeNode(preorder[startPre]); for(int i=startIn;i<=endIn;i++){ if(inorder[i] == preorder[startPre]){ root.left = helper(preorder,startPre+1,startPre+i-startIn,inorder,startIn,i-1); root.right = helper(preorder,startPre+i-startIn+1,endPre,inorder,i+1,endIn); return root; } } return null; } } 中序遍历+后序遍历同理，后序为左右根，因此后序遍历从后往前的第一个即为根节点，在中序遍历中找此根节点，同理得到左子树与右子树，再分别递归： /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return helper(inorder,0,inorder.length-1,postorder,0,postorder.length-1); } public TreeNode helper(int[] inorder,int startIn,int endIn,int[] postorder,int startPost,int endPost){ if(startIn>endIn || startPost>endPost) return null; TreeNode root = new TreeNode(postorder[endPost]); for(int i = startIn;i<=endIn;i++){ if(inorder[i] == root.val){ root.left = helper(inorder,startIn,i-1,postorder,startPost,startPost+i-startIn-1); root.right = helper(inorder,i+1,endIn,postorder,startPost+i-startIn,endPost-1); return root; } } return null; } }