剑指offer - 重建二叉树

发表于 | 更新于

题目

https://www.nowcoder.com/questionTerminal/8a19cbe657394eeaac2f6ea9b0f6fcf6

题意

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

题解

二叉树前序遍历：根-左子树-右子树，二叉树中序遍历：左子树-根-右子树，根据根节点的位置，可以将左右技子树分开，然后递归操作即可。

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
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin)
    {
        if(pre.empty()) return NULL;
        TreeNode * root = new TreeNode(pre[0]);
        int pos = find(vin.begin(),vin.end(),pre[0])-vin.begin();
        vector<int> lpre,lvin,rpre,rvin;
        //如果pos = 0，表示左子树为空
        if(pos>0){
            lpre = vector<int>(pre.begin()+1,pre.begin()+pos+1);
            lvin = vector<int>(vin.begin(),vin.begin()+pos);
        }
        //如果pos = pre.size-1 ,表示右子树为空
        if(pos<pre.size()-1){
            rpre = vector<int>(pre.begin()+pos+1,pre.end());
            rvin = vector<int>(vin.begin()+pos+1,vin.end());
        }
        root->left = reConstructBinaryTree(lpre,lvin);
        root->right = reConstructBinaryTree(rpre,rvin);
        return root;
    }
};

已知中序遍历和 前序或者后后续遍历 ，都可以唯一确定一棵二叉树，但是已知前序和后序无法确定。
如果要得到后序遍历序列，只需要在返回前打印或者存储根节点的值即可。
如果要得到层次遍历序列，可以将树建好之后用队列实现一遍。
还有一种方法，就是按照数组存储满二叉树的思想，用一个map记录，对应下标上的值，由于是map，没有节点的地方map也不会有值，不用担心存不下所有的点，但是这种方法有一个缺点，由于map key类型的限制，使用会有一定限制，比如int的key类型，只能存储31层左右的树，long long 类推。

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
class Solution
{
public:
    map<int,int> levelTravelMap;
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin,int index)
    {
        if(pre.empty()) return NULL;
        levelTravelMap[index]=pre[0];
        TreeNode * root = new TreeNode(pre[0]);
        int pos = find(vin.begin(),vin.end(),pre[0])-vin.begin();
        vector<int> lpre,lvin,rpre,rvin;
        //如果pos = 0，表示左子树为空
        if(pos>0){
            lpre = vector<int>(pre.begin()+1,pre.begin()+pos+1);
            lvin = vector<int>(vin.begin(),vin.begin()+pos);
        }
        //如果pos = pre.size-1 ,表示右子树为空
        if(pos<pre.size()-1){
            rpre = vector<int>(pre.begin()+pos+1,pre.end());
            rvin = vector<int>(vin.begin()+pos+1,vin.end());
        }
        root->left = reConstructBinaryTree(lpre,lvin,index<<1);
        root->right = reConstructBinaryTree(rpre,rvin,index<<1|1);
        return root;
    }
};