问题重述:
问题求解:
我们换一组比较有代表性的样例,
对于上图的树来说,
index: 0 1 2 3 4 5 6
先序遍历为: 1 2 4 5 3 6 7
中序遍历为: 4 2 5 1 6 3 7
为了清晰表示,我给节点上了颜色,红色是根节点,蓝色为左子树,绿色为右子树。
提取期中根节点的左子树 2 4 5,可以把2 4 5看作新的index,由此:
index: 2 4 5
先序遍历为: 2 4 5
中序遍历为: 4 2 5
同理,右子树也是如此。
这样不难看出本题应该用递归方法解决。
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { TreeNode root = null; if(preorder.length == 0) return root; root = new TreeNode(preorder[0]); if(preorder.length == 1 && inorder.length == 1) { //root.val = preorder[0]; return root; } //root.val = preorder[0]; int flag = 0; for(int i=0;i<inorder.length;i++){ if(inorder[i] == preorder[0]) { flag = i; break; } } TreeNode lNode = null; TreeNode rNode = null; root.left = buildTree(Arrays.copyOfRange(preorder,1,flag+1),Arrays.copyOfRange(inorder,0,flag)); root.right = buildTree(Arrays.copyOfRange(preorder,flag+1,preorder.length),Arrays.copyOfRange(inorder,flag+1,inorder.length)); return root; } }