剑指Offer第4题：重建二叉树

发表于 更新于 分类于

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

解题思路：在二叉树的前序遍历中，根节点总是最先出现；而中序遍历中，左子树的节点先出现。因此，我们可以先根据前序遍历中的第一个值k，构建根节点，接着在中序遍历中找到k, 则中序遍历中k左边的为左子树，右边的为右子树，然后递归的构建左右子树即可。

Python 代码

1
2
3
4
5
6
7
8
def reConstructBinaryTree(self, pre, tin):
    # write code here
    if len(pre) == 0 or len(tin) == 0: return None # 如果遍历的列表中为空，则此时达到叶子节点
    idx = tin.index(pre[0]) # 找到中序遍历中与前序遍历的第一个值相等的位置
    root = TreeNode(pre.pop(0)) # 创建根节点
    root.left = self.reConstructBinaryTree(pre, tin[:idx]) # 递归创建左子树
    root.right = self.reConstructBinaryTree(pre, tin[idx+1:]) # 递归创建右子树
    return root

使用c++实现中，由于给出的vector不能pop出第0个值，因此，先反转顺序。
c++ 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
TreeNode* reConstructBinaryTreeHelper(vector<int> &pre,vector<int> vin) {
    if (pre.empty() || vin.empty()) return NULL; // 如果遍历的列表中为空，则此时达到叶子节点
    TreeNode* tmp = new TreeNode(pre.back()); // 创建根节点
    int i=0; // 找到中序遍历中与前序遍历的第一个值相等的位置
    for (; i<vin.size(); i++) {
        if (vin[i] == pre.back()) break;
    }
    pre.pop_back(); 
    tmp->left = reConstructBinaryTreeHelper(pre, {vin.begin(), vin.begin()+i}); //递归创建左子树
    if (vin.size() == 1) tmp->right = NULL; // 递归创建右子树， 注意，若此时中序遍历中只剩一个值，{vin.begin()+i+1, vin.end()} 会出错，因此要先判断。
    else tmp->right = reConstructBinaryTreeHelper(pre, {vin.begin()+i+1, vin.end()}); 
    return tmp;
}
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
    vector<int> revpre; // 反转顺序
    while (!pre.empty()) {
        revpre.push_back(pre.back());
        pre.pop_back();
    }
    return reConstructBinaryTreeHelper(revpre, vin);
}