重建二叉树

Posted on In Views: Waline: Views: Symbols count in article: 1.2k Reading time ≈ 1 mins.

题解方法

  • 递归

递归

  1. 前序遍历的第一个节点为根节点
  2. 根据根节点将中序遍历划分为 [左子树｜根节点｜右子树]
  3. 根据中序遍历中左右子树的节点数将前序遍历划分为 [根节点｜左子树｜右子树]

核心代码

构建中序遍历索引

1
2
3
4
5
Map<Integer, Integer> idxMap = new HashMap<>();
// 构建中序遍历的索引，加快查找
for (int i = 0; i < inorder.length; i++) {
    idxMap.put(inorder[i], i);
}

递归建树

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
private TreeNode buildTree(int preStart, int preEnd, int inStart, int inEnd) {
    // 左边界大于右边界，递归终止
    if (preStart > preEnd) {
        return null;
    }
    // 前序遍历的第一个节点为根节点
    int preRootIdx = preStart;
    int rootVal = preOrder[preRootIdx];
    int inRootIdx = idxMap.get(rootVal);
    TreeNode root = new TreeNode(rootVal);
    // 前序遍历的左子树的左边界为前序遍历的第二个节点
    int preLeftStart = preStart + 1;
    // 左子树的节点数为中序遍历的根节点减去中序遍历的左边界
    int leftSize = inRootIdx - inStart;
    // 前序遍历的左子树的右边界为前序遍历的左子树的左边界加上左子树的节点数减一
    int preLeftEnd = preLeftStart + leftSize - 1;
    // 中序遍历的左子树的左边界为中序遍历的左边界
    int inLeftStart = inStart;
    // 中序遍历的左子树的右边界为中序遍历的根节点减一
    int inLeftEnd = inRootIdx - 1;
    root.left = buildTree(preLeftStart, preLeftEnd, inLeftStart, inLeftEnd);
    // 前序遍历的右子树的左边界为前序遍历的左子树的右边界加一
    int preRightStart = preLeftEnd + 1;
    // 前序遍历的右子树的右边界为前序遍历的右边界
    int preRightEnd = preEnd;
    // 中序遍历的右子树的左边界为中序遍历的根节点加一
    int inRightStart = inRootIdx + 1;
    // 中序遍历的右子树的右边界为中序遍历的右边界
    int inRightEnd = inEnd;
    root.right = buildTree(preRightStart, preRightEnd, inRightStart, inRightEnd);

    return root;
}

题目来源

剑指 Offer 07. 重建二叉树 - 力扣（LeetCode）