题解 | #重建二叉树#
重建二叉树
http://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6
算法思想一：递归
解题思路：
二叉树的前序遍历：根左右；中序遍历：左根右
由前序遍历知道根节点之后，能在中序遍历上划分出左子树和右子树。分别对中序遍历的左右子树递归进行这一过程即可建树。
由前序遍历知道根节点之后，能在中序遍历上划分出左子树和右子树。分别对中序遍历的左右子树递归进行这一过程即可建树。
图解：
代码展示：
Python版本
class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # write code here if not pre: return None # 根节点 root = TreeNode(pre[0]) # 根节点在中序遍历中的位置索引 tmp = tin.index(pre[0]) # 递归 构造树的左子树 root.left = self.reConstructBinaryTree(pre[1:tmp+1], tin[:tmp]) # 递归构造树的右子树 root.right = self.reConstructBinaryTree(pre[tmp+1:], tin[tmp+1:]) return root
复杂度分析：
时间复杂度O(N)：N表示二叉树的结点数量
空间复杂度O(N)：返回的树占用空间
算法思想二：指针
解题思路：
二叉树的前序遍历：根左右；中序遍历：左根右 设置三个指针，一个是preStart，表示的是前序遍历开始的位置，一个是inStart，表示的是中序遍历开始的位置。一个是inEnd，表示的是中序遍历结束的位置，我们主要是对中序遍历的数组进行拆解
图解：
前序序列：【1，2，3，4，5，6，7】
中序遍历：【3，2，4，1，6，5，7】
只要找到了前序遍历的结点在中序遍历的位置，我们就可以把中序遍历数组分解为左右子树两部分。
1、如果index是前序遍历的某个值在中序遍历数组中的索引，以index为根节点划分，在中序遍历中，[0，index-1]就是根节点左子树的所有节点，[index+1，tin.length-1]就是根节点右子树的所有节点
2、对于前序序列，针对左子树，preStart=index+1，如果是右子树就稍微麻烦点，preStart=preStart+(index-inStart+1)，preStart是当前节点比如m先序遍历开始的位置，index-inStart+1就是当前节点m左子树的数量加上当前节点的数量，所以preStart+(index-instart+1)就是当前节点m右子树前序遍历开始的位置
代码展示：
JAVA版本
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return dfs(0, 0, in.length - 1, pre, in);
}
public TreeNode dfs(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) {
if (preStart > preorder.length - 1 || inStart > inEnd) {
return null;
}
//创建结点
TreeNode root = new TreeNode(preorder[preStart]);
int index = 0;
//找到当前节点root在中序遍历中的位置，然后再把数组分两半
for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == root.val) { index = i; break; } } root.left = dfs(preStart + 1, inStart, index - 1, preorder, inorder); root.right = dfs(preStart + index - inStart + 1, index + 1, inEnd, preorder, inorder); return root; } 复杂度分析：
时间复杂度O(N)：N表示二叉树的结点数量
空间复杂度O(N)：返回的树空间，使用额外指针，常数级空间
算法思想三：栈
解题思路：
二叉树的前序遍历：根左右；中序遍历：左根右 借助栈来解决问题需要关注一个问题，就是前序遍历挨着的两个值比如m和n，它们会有下面两种情况之一的关系。
1、n是m左子树节点的值。
2、n是m右子树节点的值或者是m某个祖先节点的右节点的值。
对于第一种情况很容易理解，如果m的左子树不为空，那么n就是m左子树节点的值。
对于第二种情况，如果一个结点没有左子树只有右子树，那么n就是m右子树节点的值，如果一个结点既没有左子树也没有右子树，那么n就是m某个祖先节点的右节点，只要找到这个祖先节点就可以
1、n是m左子树节点的值。
2、n是m右子树节点的值或者是m某个祖先节点的右节点的值。
对于第一种情况很容易理解，如果m的左子树不为空，那么n就是m左子树节点的值。
对于第二种情况，如果一个结点没有左子树只有右子树，那么n就是m右子树节点的值，如果一个结点既没有左子树也没有右子树，那么n就是m某个祖先节点的右节点，只要找到这个祖先节点就可以
代码展示：
JAVA版本
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if (pre.length == 0)
return null;
Stackstack = new Stack<>();
//前序的第一个其实就是根节点
TreeNode root = new TreeNode(pre[0]);
TreeNode cur = root;
for (int i = 1, j = 0; i < pre.length; i++) { //第一种情况 if (cur.val != in[j]) { cur.left = new TreeNode(pre[i]); stack.push(cur); cur = cur.left; } else { //第二种情况 j++; //找到合适的cur，然后确定他的右节点 while (!stack.empty() && stack.peek().val == in[j]) { cur = stack.pop(); j++; } //给cur添加右节点 cur = cur.right = new TreeNode(pre[i]); } } return root; } } 复杂度分析：
时间复杂度O(N)：N表示二叉树的结点数量
空间复杂度O(1)：额外的栈空间（N个元素），返回树空间
