二叉树的构建.md

首先我们要知道，三种不同遍历方式的过程。看下图很容易理解，并且不容易忘。 前序遍历： 根 左 右 中序遍历： 左 根 右 后序遍历： 左 右 根

前序 + 中序

题意： 给你一个前序遍历和中序遍历，你要构造出一个二叉树。 示例：

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

要想解决这类题目，我们就要掌握遍历的特点。

1. 前序遍历第一位数字一定是这个二叉树的根结点。
2. 中序遍历中，根结点讲序列分为了左右两个区间。左边的区间是左子树的结点集合，右边的区间是右子树的结点集合。

我们能找到根节点，就能找到左子树和右子树的集合，那么这个二叉树是不是就已经有了一个大致的样子。 接下来要做的，就是使用递归去构建出左子树和右子树。

示例过程：

代码：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	//用 HashMap 存储中序遍历，目的是查找方便。因为我们从前序遍历找到根节点后，还要寻找根节点在中序遍历的哪个位置
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i],i);
        return build(preorder, map, 0, preorder.length - 1, 0);
    }

	// 传入了五个参数，分别是：先序序列，中序序列
	// 先序序列的开始，先序序列的结束，中序序列的开始
    public TreeNode build(int[] preorder, HashMap<Integer,Integer> map, int preStart, int preEnd, int inStart){
    	// 递归边界
        if(preEnd < preStart)
            return null;
        // 先序序列的第一位是根节点
        TreeNode root = new TreeNode(preorder[preStart]);
        //找到中序序列中，根节点的索引 index
        int rootIndex = map.get(root.val);
        // len 代表左子树的结点个数
        int len = rootIndex - inStart;
        // 左右子树的递归调用
        root.left = build(preorder, map, preStart + 1, preStart + len, inStart);
        root.right = build(preorder, map, preStart + len + 1, preEnd, rootIndex + 1);
        return root;
    }

后序+中序

我们会理解了前序和中序遍历构造二叉树，那么后序和中序构造二叉树就不是难事。 后序序列的特点是，左，右，根。

1. 找到根结点（后序遍历的最后一位）
2. 在中序遍历中，找到根结点的位置，划分左右子树，递归构建二叉树。

这里希望各位自行在草稿纸上画一下，二叉树构建过程。

代码：

public TreeNode buildTree(int[] inorder, int[] postorder) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++)
            map.put(inorder[i],i);
        return build(postorder, map, 0, postorder.length - 1, 0);
    }

    public TreeNode build(int[] postorder, HashMap<Integer,Integer> map, int postStart, int postEnd, int inStart){
        if(postEnd < postStart)
            return null;
        TreeNode root = new TreeNode(postorder[postEnd]);
        int rootIndex = map.get(root.val);
        int len = rootIndex - inStart;
		// 前面与先序遍历是一样的，仅仅是划分左右子树的地方不同。
        root.left = build(postorder, map, postStart, postStart + len - 1, inStart);
        root.right = build(postorder, map, postStart + len, postEnd - 1, rootIndex + 1);
        return root;
    }

两者的比较：

由图片可以很清晰的看到，前序遍历是根左右，后序遍历是左右根。代码中递归的参数传递，即划分区域就是按照这个图片得到的。没理解代码可以结合图片去看。

二叉树的问题绝大部分都是和三种遍历有关，思考问题的时候，可以从三种遍历的特点入手。

学习更多算法 + 计算机基础知识，欢迎关注我的微信公众号，每天准时推送技术干货