剑指offer：4.重建二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。牛客网oj地址

样例

1
2
3
4
5
6
7
8
9
10
11
给定：
前序遍历是：[3, 9, 20, 15, 7]
中序遍历是：[9, 3, 15, 20, 7]

返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉树如下所示：
    3
   / \
  9  20
    /  \
   15   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
class Solution {
private:
    vector<int> pre;
    vector<int> vin;
    unordered_map<int,int> theMap;
public:
    TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        this->pre=pre;
        this->vin=vin;
        int length=vin.size();
        //因为需要不断查找根节点在中序遍历中的位置，所以使用hashmap将查找复杂度降到O（1）
        for (int i = 0; i < length; ++i) {
            theMap[vin[i]]=i;
        }
        return dfs(0,length-1,0,length-1);
    }
    TreeNode * dfs(int pl,int ph,int vl,int vh){
        if(pl>ph)
            return nullptr;
        TreeNode * root=new TreeNode(pre[pl]);
        int vinIndex=theMap[pre[pl]];
        int leftLength=vinIndex-vl; //计算左子树的节点数量
        root->left=dfs(pl+1,pl+leftLength,vl,vinIndex-1);
        root->right=dfs(pl+leftLength+1,ph,vinIndex+1,vh);
        return root;
    }
};

类似题目

leetcode：106. 从中序与后序遍历序列构造二叉树。解题思路完全一致，ac代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    unordered_map<int,int> theMap;
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int length=inorder.size();
        for (int i = 0; i < length; ++i) {
            theMap[inorder[i]]=i;
        }
        return dfs(postorder,0,length-1,0,length-1);
    }
    TreeNode * dfs(const vector<int> & postorder,int pl,int ph,int il,int ih){
        if(pl>ph)
            return nullptr;
        TreeNode * root=new TreeNode(postorder[ph]);
        int vinIndex=theMap[postorder[ph]];
        int rightLength=ih-vinIndex;
        root->left=dfs(postorder,pl,ph-rightLength-1,il,vinIndex-1);
        root->right=dfs(postorder,ph-rightLength,ph-1,vinIndex+1,ih);
        return root;
    }
};