105. Construct Binary Tree from Preorder and Inorder Traversal

题目描述（中等难度）

根据二叉树的先序遍历和中序遍历还原二叉树。

解法一 递归

先序遍历的顺序是根节点，左子树，右子树。中序遍历的顺序是左子树，根节点，右子树。

所以我们只需要根据先序遍历得到根节点，然后在中序遍历中找到根节点的位置，它的左边就是左子树的节点，右边就是右子树的节点。

生成左子树和右子树就可以递归的进行了。

比如上图的例子，我们来分析一下。

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
首先根据 preorder 找到根节点是 3

然后根据根节点将 inorder 分成左子树和右子树
左子树
inorder [9]

右子树
inorder [15,20,7]

把相应的前序遍历的数组也加进来
左子树
preorder[9] 
inorder [9]

右子树
preorder[20 15 7] 
inorder [15,20,7]

现在我们只需要构造左子树和右子树即可，成功把大问题化成了小问题
然后重复上边的步骤继续划分，直到 preorder 和 inorder 都为空，返回 null 即可

事实上，我们不需要真的把 preorder 和 inorder 切分了，只需要用分别用两个指针指向开头和结束位置即可。注意下边的两个指针指向的数组范围是包括左边界，不包括右边界。

对于下边的树的合成。

左子树

右子树

class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x){val=x;}
}
public class Construct_Binary_Tree_from_Preorder_and_Inorder {
	
	public static TreeNode buildTree(int[] preorder,int[]inorder) {
		return builderTreeHelper(preorder,0,preorder.length,inorder,0,inorder.length);
	}
	
	private static TreeNode builderTreeHelper(int[] preorder,int p_start,int p_end,int[] inorder,int i_start,int i_end) {
		if(p_start==p_end) return null;
		
		int root_val=preorder[p_start];
		TreeNode root=new TreeNode(root_val);
		//在中序遍历中找到根节点的位置
		int i_root_index=0;
		for(int i=i_start;i<i_end;i++) {
			if(root_val==inorder[i]) {
				i_root_index=i;
				break;
			}
		}
		int leftNum=i_root_index-i_start;
		//递归的构造左子树
		root.left=builderTreeHelper(preorder,p_start+1,p_start+leftNum+1,inorder,i_start,i_root_index);
		//递归的构造左子树
		root.right=builderTreeHelper(preorder,p_start+leftNum+1,p_end,inorder,i_root_index+1,i_end);
		return root;
	}
	public static void main(String args[]) {
		int[] preorder= {3,9,20,15,7};
		int[] inorder= {9,3,15,20,7};
		
		TreeNode ans=buildTree(preorder,inorder);
		System.out.println(ans.val);
	}
}

上边的代码很好理解，但存在一个问题，在中序遍历中找到根节点的位置每次都得遍历中序遍历的数组去寻找，参考这里 ，我们可以用一个HashMap把中序遍历数组的每个元素的值和下标存起来，这样寻找根节点的位置就可以直接得到了。

import java.util.HashMap;

public class Construct_Binary_Tree_from_Preorder_and_Inorder2 {
	
	public static TreeNode buildTree(int[] preorder,int[] inorder) {
		HashMap<Integer,Integer>map=new HashMap<>();
		for(int i=0;i<inorder.length;i++) {
			map.put(inorder[i], i);//相当于python中的dict
		}
		return builderHelper(preorder,0,preorder.length,inorder,0,inorder.length,map);
	}

	
	private static TreeNode builderHelper(int[] preorder, int p_start, int p_end, int[] inorder, int i_start, int i_end,
			HashMap<Integer, Integer> map) {
		if(p_start==p_end) return null;
		
		int root_val=preorder[p_start];
		TreeNode root=new TreeNode(root_val);
		int i_root_index=map.get(root_val);
		int leftNum=i_root_index-i_start;
		root.left=builderHelper(preorder,p_start+1,p_start+1+leftNum,inorder,i_start,i_root_index,map);
		root.right=builderHelper(preorder,p_start+1+leftNum,p_end,inorder,i_root_index+1,i_end,map);
		
		return root;
	}

	public static void main(String args[]) {
		int[] preorder= {3,9,20,15,7};
		int[] inorder= {9,3,15,20,7};
		
		TreeNode ans=buildTree(preorder,inorder);
		System.out.println(ans.val);
	}
}

总结

用常规的递归和 HashMap 做的话这道题可以很容易解决。

参考文献

1.https://zhuanlan.zhihu.com/p/74214340
2.https://www.youtube.com/watch?v=S1wNG5hx-30