剑指 Offer 07. 重建二叉树

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]
 

限制：

0 <= 节点个数 <= 5000

img

思路

先按照题目自己构建一个二叉树，不考虑代码实现

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

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

  1. 前序遍历一定能够确定3是根节点
  2. 这样在中序遍历中，3左边的值一定是这个根节点的左子树，3右边的值一定是根的右子树
  3. 3左边只有一个数9，说明这个数的左子树只有一个是9
  4. 3的右子树有三个值，（15,20,7），然后在看前序遍历，前序遍历中的（20,15,7）一定是根的右子树，所以20一定是3的右孩子
  5. 然后在看中序遍历，20是右孩子的根节点，那么15一定是20的左孩子，7一定是20的右孩子
  6. 最后代入前序遍历验证
  7. 正确

所以一个前序一定能确定一个根，然后在结合后续一定能确定根的左右孩子，这样在去前序遍历和中序遍历中对比，那么一定能构建一个二叉树

实现

不要看下面代码感觉挺多的，其实很简单就是一个递归的过程，只是传递的参数多，然后一行放不下了而已

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
   public TreeNode buildTree(int[] preorder, int[] inorder) {
        //构建map结构是因为，在每次在中序数组中中查找当前根节点都要遍历一次，这样可以避免遍历，直接拿到当前根节点的index
        HashMap<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        int length = inorder.length;
        for (int i = 0; i < length; i++) {
            indexMap.put(inorder[i], i);
        }
        TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
        return root;
    }

    private TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, HashMap<Integer, Integer> indexMap) {
        //递归终止条件
        if (preorderStart > preorderEnd) {
            return null;
        }
        //先找出根节点
        int rootVal = preorder[preorderStart];
        //然后在中序遍历中找到根节点的位置，之前一定是根节点的左子树，之后一定是根节点的右子树
        //构建树的根节点
        TreeNode root = new TreeNode(rootVal);
        //如果左节点的长度为零，说明这个就是根节点，且没有子节点，直接返回
        if (preorderStart == preorderEnd) {
            return root;
        } else {
            //拿到根节点在中序遍历数组的索引
            int rootIndex = indexMap.get(rootVal);
            //拿到根节点的索引后，可以在前序遍历中拿到根节点左孩子的数量（最后一个节点的index），和右孩子的数量（）
            // 然后就需要对，根节点的左子树部分进行构建
            // 需要找到左子树中对应的前序遍历和中序遍历，分别对应的数组的位置
            /**
             * 1. 前序遍历的数组还是这个数组
             * 2. 左子树中在前序遍历数组的开始索引：preorderStart + 1，根节点左边的第一个节点就是左子树的第一个索引位置
             * 3. 左子树中在前序遍历数组结束的索引：preorderStart + (rootIndex - inorderStart)，
             *  根节点 + 在中序遍历中根节点距离开始节点的位置  = 根节点 + （在中序遍历中根节点的索引 - 在中序遍历中开始的索引）
             * 4. 中序遍历数组还是这个数组
             * 5. 左子树中在中序遍历数组的开始索引：inorderStart，中序遍历数组中的开始位置
             * 6. 左子树中在中序遍历数组结束的索引：rootIndex - 1，根节点索引位置减一
             *
             */
            TreeNode leftNode = buildTree(preorder, preorderStart + 1, preorderStart + (rootIndex - inorderStart),
                    inorder, inorderStart, rootIndex - 1, indexMap);
            //需要找到右子树中对应的前序遍历和中序遍历，分别对应的数组的位置

            /**
             * 1. 前序遍历的数组还是这个数组
             * 2. 右子树中在前序遍历数组的开始索引：preorderEnd - (inorderEnd - rootIndex) + 1，
             * 前序遍历数组的末尾索引 - 右子树数的数量 + 1  = 前序遍历数组的末尾索引 - （中序遍历末尾位置 - 中序遍历根节点的索引 ） + 1
             * 3. 右子树中在前序遍历数组结束的索引：preorderEnd，
             * 4. 中序遍历数组还是这个数组
             * 5. 右子树中在中序遍历数组的开始索引：rootIndex + 1，根节点索引位置加一
             * 6. 右子树中在中序遍历数组结束的索引：inorderEnd，
             *
             */
            TreeNode rightNode = buildTree(preorder, preorderEnd - (inorderEnd - rootIndex) + 1, preorderEnd,
                    inorder, rootIndex + 1, inorderEnd, indexMap);
            root.left = leftNode;
            root.right = rightNode;
            return root;
        }
    }
}

重点有一个地方：

收获

二叉树的前序、中序、后序遍历

小学数学加减法

求左子树中在前序遍历数组结束的索引和右子树中在前序遍历数组的开始索引

这里为什么有的地方加一，有的地方不加一，而有的地方需要减一

这个是在算法中经常会遇到的问题：

其实还是小学数学：

请听题：

一个有六棵树分别叫，0号，1号 ，2号，3号，4号，5号

  1. 5号和2号间有几颗树

    1
    (5 - 2) - 1 = 2

  2. 2号树向右移动几次能到达5号树的位置

    1
    5 - 2 = 3

  3. 5号树向右移动两次是第几颗树

    1
    (5 - 2) + 1 = 4

    因为索引是从0开始的，所以引号加1，如果索引不是从零开始的直接间就可以了

总结

  1. 两个数之间的差值，为小的数向大的数移动的次数
  2. 如果要求两个数之间的数字数量，需要差值减一

博客首先发布于：

https://lvxiaoyi.top/