VIRTUALS

the virtual labs for the virtuals

0%

剑指Offer 07. 重建二叉树

Posted on Edited on In , , ,

摘要：
根据二叉树的前序遍历结果和中序遍历结果重建二叉树，一道非常好的题目。

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

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

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

限制：
$ 0 <= 节点个数 <= 5000 $

树的定义：

1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
1
2
3
4
5
6
7
8
9
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

递归

构建二叉树的一般作法是：先构建根节点，再递归构建根节点的左右孩子节点。

首先设二叉树共有 $n + m + 1$ 个节点，其中根节点的左子树共有 $n$ 个节点，右子树共有 $m$ 个节点。

前序遍历数组的第一个数一定是二叉树的根节点值，从第二个数开始到第$n$个数结束，为结点数为$n$的左子树的所有节点值；从第$n+1$个数开始，到第$n+m$个数结束，为结点数为$m$的右子树所有节点值。

中序遍历数组的第$0$个数开始，到第$n-1$个数结束，为结点数为$n$的左子树的所有节点值；第$n$个数为整个二叉树的根节点值；从第$n+1$个数开始，到 $n + m$ 个数结束，为结点数为$m$的右子树所有节点值。

根据前序遍历数组，我们必然得知根节点值，由于二叉树的每个节点值不同，可以根据根节点值在中序数组中找到其位置，将中序数组一分为二。那么左半边全是左子树节点值，右半边为右子树节点值。根据这一信息计算出左右子树长度。

回到前序数组中，可以注意到第一个节点值为根节点，第二个结点为左子树根节点。我们发现左子树的根节点永远在根节点右边偏移一位的位置。同时可以根据根节点加上左子树长度的偏移找到右子树根节点。

至此，我们完成了一个：构建根节点，构建根节点左孩子节点，构建根节点右孩子节点的过程。
此后，可以递归地完成整个二叉树的构建。

在构建过程中，可以维护一个指针对 l r 分别在两个遍历序列中指向树的节点范围起始边界和结束边界。在递归构建过程中，分别缩小这两个指针指向的范围以达到构建子树的目的。

在中序遍历数组中，左子树的左边界始终对应当前树的左边界，左子树的右边界始终对应当树根节点位置左边一位；
右子树的右边界始终对应当前树的右边界，右子树的左边界始终对应当前树根节点位置右边一位。

在前序遍历数组中，左子树的左边界对应左子树根节点位置，当左子树的左边界大于左子树的右边界，则该分支结束；
右子树的左边界可以根据左子树长度计算得到，右子树左边界大于右边界，则该分支结束。

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
// 执行用时: 20 ms
// 内存消耗: 24.8 MB
class Solution {
public:
    unordered_map<int, int> hash;
    int len;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        len = inorder.size();
        for (int i = 0; i < len; i++) {
            hash[inorder[i]] = i;
        }
        
        return helper(preorder, inorder, 0, len - 1, 0, len - 1);
        
    }

    TreeNode* helper(vector<int>& preorder, vector<int>& inorder, int lp, int rp, int li, int ri) {
        if (lp > rp) return nullptr;
        // build root
        TreeNode* root = new TreeNode(preorder[lp]);

        int inIndexRoot = hash[preorder[lp]];
        // length of left/right sub-tree
        int llen = inIndexRoot - li;
        int rlen = ri - inIndexRoot;

        // build left/right sub-tree
        root->left = helper(preorder, inorder, lp + 1, lp + 1 + llen - 1, li, inIndexRoot - 1);
        root->right = helper(preorder, inorder, lp + llen + 1, lp + llen + 1 + rlen - 1, inIndexRoot + 1, ri); 
        return root;
    }
};
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
// 执行用时: 2 ms
// 内存消耗: 38.6 MB
class Solution {
    Map<Integer, Integer> hash = new HashMap<>();
    int len;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        len = preorder.length;
        for (int i = 0; i < len; i++) {
            hash.put(inorder[i], i);
        }
        return helper(preorder, inorder, 0, len - 1, 0, len - 1);
    }

    private TreeNode helper(int[] preorder, int[] inorder, int lp, int rp, int lin, int rin) {
        if (lp > rp) return null;

        int rootVal = preorder[lp];
        int rootIndexIn = hash.get(rootVal);

        TreeNode root = new TreeNode(rootVal);
        
        int llen = rootIndexIn - lin;
        int rlen = rin - rootIndexIn;

        root.left = helper(preorder, inorder, lp + 1, lp + 1 + llen - 1, lin, rootIndexIn - 1);
        root.right = helper(preorder, inorder, lp + 1 + llen, rp, rootIndexIn + 1, rin);
        return root;
    } 
}

原题链接： 剑指Offer 07. 重建二叉树