【LeetCode】105. 根据一棵树的前序遍历与中序遍历构造二叉树。（同剑指 Offer 07）
一、题目
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 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 构建左右子树：开启左右子树递归
| 根节点索引 | 中序遍历左边界 | 中序遍历右边界 | |
|---|---|---|---|
| 左子树 | root+1 | left | i-1 |
| 右子树 | i-left+root+1 | i+1 | right |
代码-版本1：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */classSolution{int[]preorder;HashMap<Integer,Integer>dic=newHashMap<>();publicTreeNodebuildTree(int[]preorder,int[]inorder){this.preorder=preorder;for(inti=0;i<inorder.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(inLeft>inRight)returnnull;TreeNoderoot=newTreeNode(preorder[preRoot]);// 根节点在中序序列中的位置，用于划分左右子树的边界intinRoot=dic.get(preorder[preRoot]);// 左子树在前序中的根节点位于：preRoot+1,左子树在中序中的边界：[inLeft, inRight-1]root.left=build(preorder,inorder,preRoot+1,inLeft,inRoot-1);// 右子树在前序中的根节点位于：根节点+左子树长度+1 = preRoot+inRoot-inLeft+1// 右子树在中序中的边界：[inRoot+1,inRight]root.right=build(preorder,inorder,preRoot+inRoot-inLeft+1,inRoot+1,inRight);returnroot;}}代码-版本2：（对版本1 代码进一步精简后）
classSolution{int[]preorder;HashMap<Integer,Integer>dic=newHashMap<>();publicTreeNodebuildTree(int[]preorder,int[]inorder){this.preorder=preorder;for(inti=0;i<inorder.length;i++)dic.put(inorder[i],i);returnrecur(0,0,inorder.length-1);}publicTreeNoderecur(intpreRoot,intinLeft,intinRight){if(inLeft>inRight)returnnull;// 递归终止TreeNodenode=newTreeNode(preorder[preRoot]);// 建立根节点// 根节点在中序序列中的位置，用于划分左右子树的边界intinRoot=dic.get(preorder[preRoot]);// 划分根节点、左子树、右子树// 左子树在前序中的根节点位于：preRoot+1, 左子树在中序中的边界：[in_left,in_root-1]node.left=recur(preRoot+1,inLeft,inRoot-1);// 开启左子树递归node.right=recur(preRoot+inRoot-inLeft+1,inRoot+1,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_1x1；
- x 0 x_0x0没有左儿子，x 1 x_1x1是x 0 x_0x0或x 0 x_0x0的祖先节点的右儿子。后一种情况是因为x 0 x_0x0没有右儿子，就会往上回溯，直到遇到有第一个右儿子的节点 –x 0 ′ x_0'x0′（可能就是x 0 x_0x0），那么x 1 x_1x1就是x 0 ′ x_0'x0′的右儿子。
已知：
- 先序遍历preOrder：【根节点】【左子树】【右子树】
- 中序遍历inOrder：【左子树】【根节点】【右子树】
推论：
- 1：在preOrder第一个右孩子节点之前，碰到的preOrder与inOrder的节点交集，他们顺序正好相反。
例1（说明推论1）： preorder=[3,9,20,15,7]inorder=[20,9,15,3,7]构造树：3972015这里preOrder遇到的第一个右孩子是15，那此前碰到节点的交集为{3，9，20}， 可以看到preOrder{3，9，20}与inOrder{20，9，3}的顺序正好相反。 构造树补充：1、怎么看出9在3的左子树？ 反证法。如果9在右子树，那么inOrder第一个节点一定是3，结果不是，所以在左子树。2、这里preOrder遇到的第一个右孩子是15，那此前碰到节点的交集为{3，9，20}， 可以看到preOrder{3，9，20}与inOrder{20，9，3}的顺序正好相反。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之前的节点交集{3，9，20}在preOrder与inOrder{20，9，3}中出现顺序相反。 反转preOrder后，{20，9，3}，此时inOrder{20，9，15，3}，说明9是15的父节点。 再详细说明下，已经构造出了树：3920由推论1中的补充-3可知，15是右孩子。现在需要判断15是谁的右孩子，可能是3、9、20中的一个。1）3。15是3的右孩子，则中序遍历15应该在3之后，结果为[20,9,3,15...]，对比下，与实际不符。1）9。15是9的右孩子，则中序遍历15应该在9之后，结果为[20,9,15,3,...]，对比下，与实际相符。1）20。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.length==0)returnnull;Stack<TreeNode>roots=newStack<TreeNode>();intpre=0,in=0;// 先序遍历第一个值作为根节点TreeNodecurRoot=newTreeNode(preorder[pre]);TreeNoderoot=curRoot;roots.push(curRoot);pre++;// 遍历前序遍历的数组while(pre<preorder.length){// 出现了当前节点的值和中序遍历数组的值相等，寻找是谁的右子树if(curRoot.val!=inorder[in]){// 否则的话就一直作为左子树curRoot.left=newTreeNode(preorder[pre]);curRoot=curRoot.left;roots.push(curRoot);pre++;}else{// 每次进行出栈，实现倒着遍历while(!roots.isEmpty()&&roots.peek().val==inorder[in]){curRoot=roots.peek();roots.pop();in++;}// 设为当前的右孩子curRoot.right=newTreeNode(preorder[pre]);//更新 curRootcurRoot=curRoot.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、从前序与中序遍历序列构造二叉树