题目描述
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
示例:
例如,给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3 / \ 9 20 / \ 15 7
思路
1.二叉树前序遍历数组中的第一个元素是根节点的值。
2.在二叉树中序遍历的数组中,找到根的位置,根的左边就是左子树的集合,右边就是右子树的集合,递归下去即可。
3.具体执行过程,可以参考下图。
Java代码实现
public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1); } private TreeNode buildTree(int[] preorder, int preStart,int preEnd, int[] inorder,int inStart,int inEnd) { if(preStart>preEnd || inStart>inEnd) return null; //根 int rootVal = preorder[preStart]; int i; //在中序中寻找根的位置 for (i = 0; i <= inEnd-inStart; i++) { if(inorder[inStart+i] == rootVal) break; } TreeNode root = new TreeNode(rootVal); root.left = buildTree(preorder,preStart+1,preStart+i,inorder,inStart,inStart+i-1); root.right = buildTree(preorder,preStart+i+1,preEnd,inorder,inStart+i+1,inEnd); return root; }