通过前序+中序和后序+中序来构建二叉树
- 2019 年 12 月 24 日
- 筆記
首先我们要知道，三种不同遍历方式的过程。看下图很容易理解，并且不容易忘。 前序遍历：根 左 右 中序遍历：左 根 右 后序遍历：左 右 根
在这里插入图片描述
前序 + 中序
题意：给你一个前序遍历和中序遍历，你要构造出一个二叉树。 示例：
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
要想解决这类题目，我们就要掌握遍历的特点。
- 前序遍历第一位数字一定是这个二叉树的根结点。
- 中序遍历中，根结点讲序列分为了左右两个区间。左边的区间是左子树的结点集合，右边的区间是右子树的结点集合。
我们能找到根节点，就能找到左子树和右子树的集合，那么这个二叉树是不是就已经有了一个大致的样子。 接下来要做的，就是使用递归去构建出左子树和右子树。
示例过程：
1
2
3 代码：
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; }
后序+中序
我们会理解了前序和中序遍历构造二叉树，那么后序和中序构造二叉树就不是难事。 后序序列的特点是，左，右，根。
- 找到根结点（后序遍历的最后一位）
- 在中序遍历中，找到根结点的位置，划分左右子树，递归构建二叉树。
这里希望各位自行在草稿纸上画一下，二叉树构建过程。
代码：
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; }
两者的比较：
前序遍历
在这里插入图片描述
由图片可以很清晰的看到，前序遍历是根左右，后序遍历是左右根。代码中递归的参数传递，即划分区域就是按照这个图片得到的。没理解代码可以结合图片去看。
二叉树的问题绝大部分都是和三种遍历有关，思考问题的时候，可以从三种遍历的特点入手。
其他二叉树相关
1、详解算法之重建二叉树 2、二叉树的后序遍历（非递归版） 3、二叉树的先序遍历（非递归版） 4、二叉树的中序遍历（非递归版） 5、从上往下打印二叉树 6、二叉搜索树的后序遍历序列 7、剑指offer：二叉树镜像 8、剑指offer：二叉树的子结构 9、剑指offer：重建二叉树
