一、题目注意:你可以假设树中没有重复的元素。例如给出前序遍历 preorder[3,9,20,15,7]中序遍历 inorder[9,3,15,20,7]返回如下的二叉树3/\920/\157二、解决1、递归思路前序遍历【根节点】【左子树】【右子树】中序遍历【左子树】【根节点】【右子树】推论1、前序遍历首元素为树的根节点node的值2、中序遍历中搜索node索引然后以此为界可将中序遍历划分为【左子树】【根节点】【右子树】记录左、右子树的节点数量leftCnt rightCnt。3、根据leftCnt rightCnt可以将前序遍历划分为【根节点】【左子树】【右子树】。过程递推参数前序遍历索引root、子树在中序遍历左边界left、子树在中序遍历的有边界right终止条件left right代表越过根节点此时返回null递归工作3.1. 建立根节点node节点值为preorder[root];3.2. 划分左右子树查找根节点在中序遍历inorder中的索引 i 为提升效率本文使用哈希表dic存储中序遍历的值与索引的映射查找操作的时间复杂度为O(1)3.3 构建左右子树开启左右子树递归根节点索引中序遍历左边界中序遍历右边界左子树root1lefti-1右子树i-leftroot1i1right代码-版本1/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val x; } * } */classSolution{int[]preorder;HashMapInteger,IntegerdicnewHashMap();publicTreeNodebuildTree(int[]preorder,int[]inorder){this.preorderpreorder;for(inti0;iinorder.length;i)dic.put(inorder[i],i);// return recur(0, 0, inorder.length - 1);// 传入参数前序,中序前序序列根节点中序序列左边界中序序列右边界returnbuild(preorder,inorder,0,0,inorder.length-1);}privateTreeNodebuild(int[]preorder,int[]inorder,intpreRoot,intinLeft,intinRight){// preRoot当前子树根节点在 preorder 中的位置 inLeft当前子树在 inorder 中的左边界 inRight当前子树在 inorder 中的右边界if(inLeftinRight)returnnull;TreeNoderootnewTreeNode(preorder[preRoot]);// 根节点在中序序列中的位置用于划分左右子树的边界intinRootdic.get(preorder[preRoot]);// 左子树在前序中的根节点位于preRoot1,左子树在中序中的边界[inLeft, inRight-1]root.leftbuild(preorder,inorder,preRoot1,inLeft,inRoot-1);// 右子树在前序中的根节点位于根节点左子树长度1 preRootinRoot-inLeft1// 右子树在中序中的边界[inRoot1,inRight]root.rightbuild(preorder,inorder,preRootinRoot-inLeft1,inRoot1,inRight);returnroot;}}代码-版本2对版本1 代码进一步精简后classSolution{int[]preorder;HashMapInteger,IntegerdicnewHashMap();publicTreeNodebuildTree(int[]preorder,int[]inorder){this.preorderpreorder;for(inti0;iinorder.length;i)dic.put(inorder[i],i);returnrecur(0,0,inorder.length-1);}publicTreeNoderecur(intpreRoot,intinLeft,intinRight){if(inLeftinRight)returnnull;// 递归终止TreeNodenodenewTreeNode(preorder[preRoot]);// 建立根节点// 根节点在中序序列中的位置用于划分左右子树的边界intinRootdic.get(preorder[preRoot]);// 划分根节点、左子树、右子树// 左子树在前序中的根节点位于preRoot1, 左子树在中序中的边界[in_left,in_root-1]node.leftrecur(preRoot1,inLeft,inRoot-1);// 开启左子树递归node.rightrecur(preRootinRoot-inLeft1,inRoot1,inRight);// 开启右子树递归returnnode;// 回溯返回根节点}}时间复杂度O ( n ) O(n)O(n)空间复杂度O ( n ) O(n)O(n)2、迭代思路迭代法很巧妙但同时比较晦涩不容易理解。给定先序遍历结果为x 0 , x 1 x_0, x_1x0,x1得到两个节点的可能关系有x 1 x_1x1是x 0 x_0x0的左儿子。因为遍历到x 0 x_0x0之后下一个遍历节点就是x 0 x_0x0的左儿子即x 1 x_1x1x 0 x_0x0没有左儿子x 1 x_1x1是x 0 x_0x0或x 0 x_0x0的祖先节点的右儿子。后一种情况是因为x 0 x_0x0没有右儿子就会往上回溯直到遇到有第一个右儿子的节点 –x 0 ′ x_0x0′可能就是x 0 x_0x0那么x 1 x_1x1就是x 0 ′ x_0x0′的右儿子。已知先序遍历preOrder【根节点】【左子树】【右子树】中序遍历inOrder【左子树】【根节点】【右子树】推论1在preOrder第一个右孩子节点之前碰到的preOrder与inOrder的节点交集他们顺序正好相反。例1说明推论1 preorder[3,9,20,15,7]inorder[20,9,15,3,7]构造树3972015这里preOrder遇到的第一个右孩子是15那此前碰到节点的交集为{3920} 可以看到preOrder{3920}与inOrder{2093}的顺序正好相反。 构造树补充1、怎么看出9在3的左子树 反证法。如果9在右子树那么inOrder第一个节点一定是3结果不是所以在左子树。2、这里preOrder遇到的第一个右孩子是15那此前碰到节点的交集为{3920} 可以看到preOrder{3920}与inOrder{2093}的顺序正好相反。3、如何看出15是右孩子 preorder[3,9,20,15,7]inorder[20,9,15,3,7]根据补充-1可以构造出树3920此时preOrder与inOrder的节点值一样都是20.这说明什么呢 说明下一个节点15不是左子树了。反证法如果是左子树的话那inorder中15应该出现在20之前了。2在preOrder第一个右孩子节点之前将preOrder遇到的左孩子节点不断入栈【stack】。然后从stack不断抛出节点来判断第一个右孩子的父节点是哪个。这里需要与inOrder的节点进行比较。出栈顺序与中序遍历相同的preOrder交集翻转一下的节点集合中右孩子right之前的第一个节点father就是right的父节点。例2说明推论2 preorder[3,9,20,15,7]inorder[20,9,15,3,7]构造树3972015分析 推论1分析中遇到15之前的节点交集{3920}在preOrder与inOrder{2093}中出现顺序相反。 反转preOrder后{2093}此时inOrder{209153}说明9是15的父节点。 再详细说明下已经构造出了树3920由推论1中的补充-3可知15是右孩子。现在需要判断15是谁的右孩子可能是3、9、20中的一个。13。15是3的右孩子则中序遍历15应该在3之后结果为[20,9,3,15...]对比下与实际不符。19。15是9的右孩子则中序遍历15应该在9之后结果为[20,9,15,3,...]对比下与实际相符。120。15是20的右孩子则中序遍历15应该在20之后结果为[20,15,9..]对比下与实际不符。算法流程小结1左孩子不断入栈。preOrder节点不断入栈【stack】直到遇到与inOrder中指针所在位置的值相等【stack.peek()inOrder.firstElement】不相等的时候就遇到了第一个右孩子节点。2判断右孩子的父节点。判断出第一个右孩子后倒序遍历preOrder与inOrder的交集通过stack.pop()实现找到最后一次相等的位置即为右孩子的父节点。代码classSolution{publicTreeNodebuildTree(int[]preorder,int[]inorder){if(preorder.length0)returnnull;StackTreeNoderootsnewStackTreeNode();intpre0,in0;// 先序遍历第一个值作为根节点TreeNodecurRootnewTreeNode(preorder[pre]);TreeNoderootcurRoot;roots.push(curRoot);pre;// 遍历前序遍历的数组while(prepreorder.length){// 出现了当前节点的值和中序遍历数组的值相等寻找是谁的右子树if(curRoot.val!inorder[in]){// 否则的话就一直作为左子树curRoot.leftnewTreeNode(preorder[pre]);curRootcurRoot.left;roots.push(curRoot);pre;}else{// 每次进行出栈实现倒着遍历while(!roots.isEmpty()roots.peek().valinorder[in]){curRootroots.peek();roots.pop();in;}// 设为当前的右孩子curRoot.rightnewTreeNode(preorder[pre]);//更新 curRootcurRootcurRoot.right;roots.push(curRoot);pre;}}returnroot;}}时间复杂度O ( n ) O(n)O(n)n 为树节点数量。空间复杂度O ( n ) O(n)O(n)最差情况下树退化为链表递归深度达到n最好情况下树为满二叉树递归深度为l o g n lognlogn。三、参考1、面试题07. 重建二叉树递归法清晰图解2、详细通俗的思路分析多解法3、从前序与中序遍历序列构造二叉树
