LeetCode105.从前序和中序遍历序列构造二叉树

 这道题看完题想了几分钟就想到大概的思路了，但是在写的时候有很多细节没注意出了很多问题，然后写了1个多小时，其实这道题挺简单的。

首先，最基本的知识，先序遍历是根左右，中序遍历是左根右，那么我们一眼可以知道：根节点是先序遍历的第一个节点，然后又可以在中序遍历中找到这个根节点(树中每个val都不相等)，中序遍历中根节点的左变是左子树，根节点的右遍是右子树。

那么这个题目应该怎么解呢？首先，对于树的题目要么递归要么用队列或栈，我选择用递归。根据上面发现的几个点，我想到了递归函数：

public TreeNode dfs(int[] preorder, int[] inorder)

通过这两个遍历序列我们可以创建出根节点，然后我们在从preorder和inorder中找出来左子树的leftPreorder和leftInorder以及右子树的rightPreorder和rightInorder,然后利用递归

root.left=dfs(leftPreorder, leftInorder);
root.right = dfs(rightPreorder, rightInorder);

大体上的思路就是这样，那么我们如何找出左右子树的前序和中序的遍历序列呢？

首先中序遍历是非常简单的，中序遍历是左根右的顺序，它对于每颗树都是根左右的顺序，所以‘左’就是左子树的中序遍历结果，所以我们在inorder中根节点左边就是leftInorder,根节点右边就是rightInorder。

前序遍历也不难，前序遍历是根左右，preorder第0个数是根节点，后面是左和右，而我们在中序遍历中已经知道了左子树的长度leftLength和右子树的长度rightLength，所有从第1个数往后数leftLength就是左子树的前序遍历leftPreorder，剩下的就是右子树的前序遍历rightPreorder。

然后需要注意的就是，递归的结束，如果左子树的长度小于0就不用递归的创建左子树了，右子树同理，最后返回root。以下是我的代码：

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if(preorder.length == 0){return null;}else{return dfs(preorder, inorder);}}public TreeNode dfs(int[] preorder, int[] inorder){TreeNode root = new TreeNode(preorder[0]);int leftInorderIndex = 0;int rightInorderIndex = 0;int leftPreorderIndex = 0;int rightPreorderIndex = 0;//在中序遍历中找到根节点for(int i=0;i<inorder.length;i++){if(inorder[i] == root.val){leftInorderIndex = i-1;rightInorderIndex = i+1;break;}}//找到左子树长度和右子树长度int leftLength = leftInorderIndex+1;int rightLength = inorder.length - rightInorderIndex;if(leftLength > 0){//创建leftInorderint[] leftInorder = new int[leftLength];for(int i=0;i<leftInorder.length;i++){leftInorder[i] = inorder[i];}//创建leftPreorderint[] leftPreorder = new int[leftLength];int index =1;for(int i=0;i<leftPreorder.length;i++){leftPreorder[i] = preorder[index];index++;}//递归出根节点的左子树root.left = dfs(leftPreorder, leftInorder);}if(rightLength > 0){//创建出rightInorderrightPreorderIndex = leftLength+1;int[] rightInorder = new int[rightLength];int index0= rightInorderIndex;for(int i=0;i<rightInorder.length;i++){rightInorder[i] = inorder[index0];index0++;}//创建出rightPreorderint[] rightPreorder = new int[rightLength];int index1 = rightPreorderIndex;for(int i=0;i<rightPreorder.length;i++){rightPreorder[i] = preorder[index1];index1++;}//递归出根节点的右子树root.right = dfs(rightPreorder, rightInorder);}return root;}
}

看看官方题解做法：

题解的方法一用的也是递归，但是他用了一个HashMap来快速定位根节点，还有就是他没有去创建左右子树的前中遍历序列数组，他直接传前序，中序遍历在inorder中的起始下标和终止下标，因为他们在数组中是连续的，这样全局只需要用这个最大的inorder和preorder就可以，不用花费时间和空间去创建数组，以下是题解方法一代码：

class Solution {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍历中的第一个节点就是根节点int preorder_root = preorder_left;// 在中序遍历中定位根节点int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根节点建立出来TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子树中的节点数目int size_left_subtree = inorder_root - inorder_left;// 递归地构造左子树，并连接到根节点// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 递归地构造右子树，并连接到根节点// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 构造哈希映射，帮助我们快速定位根节点indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);}
}

题解的第二种方法是迭代，

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || preorder.length == 0) {return null;}TreeNode root = new TreeNode(preorder[0]);Deque<TreeNode> stack = new LinkedList<TreeNode>();stack.push(root);int inorderIndex = 0;for (int i = 1; i < preorder.length; i++) {int preorderVal = preorder[i];TreeNode node = stack.peek();if (node.val != inorder[inorderIndex]) {node.left = new TreeNode(preorderVal);stack.push(node.left);} else {while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {node = stack.pop();inorderIndex++;}node.right = new TreeNode(preorderVal);stack.push(node.right);}}return root;}
}