一、重建二叉树

利用前序和中序遍历的结果重构二叉树

解法一:递归(推荐)

• 先由前序遍历的第一个点创建根节点‘
• 遍历中序遍历结果查找根节点在数组中的位置
• 按照子树节点数将两个遍历数组分割为子数组，子数组递归再构建子树根节点，重复以上操作
• 直到子树序列长度为0，结束递归

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n=pre.size(),m=vin.size();
        if(n==0||m==0)
            return NULL;
        TreeNode*root=new TreeNode(pre[0]);//构建根节点
        for(int i=0;i<vin.size();i++)
        {
            if(pre[0]==vin[i])//找到中序遍历里前序遍历的第一个元素，分割序列
            {
                vector<int>leftpre(pre.begin()+1,pre.begin()+i+1);//左子树前序遍历
                vector<int>leftvin(vin.begin(),vin.begin()+i);//左子树中序遍历
                vector<int>rightpre(pre.begin()+i+1,pre.end());//右子树前序遍历
                vector<int>rightvin(vin.begin()+i+1,vin.end());//右子树中序遍历
                root->left=reConstructBinaryTree(leftpre, leftvin);//构建左子树
                root->right=reConstructBinaryTree(rightpre, rightvin);//构建右子树
            }
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度:O(n),递归构建节点n次
空间复杂度:O(n),递归栈最大深度不超过n，辅助数组长度也不超过n

解法二:栈

• 首先前序遍历第一个节点为根节点，建立辅助栈
• 前序遍历中相邻的两个数字只存在两种情况，一是，后一个是前一个的左节点，另一种是后一个是前一个的右节点或其祖先的右节点，据此判断
• 同时遍历两个序列，判段是否为左节点，若是则继续向左判断，用栈记录祖先，若不是，出栈回到相应祖先，进入右子树判断
  

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n=pre.size(),m=vin.size();
        if(n==0||m==0)
            return NULL;
        stack<TreeNode*>s;
        TreeNode*root=new TreeNode(pre[0]);//建立根节点
        TreeNode*cur=root;
        for(int i=1,j=0;i<n;i++)
        {
            if(cur->val!=vin[j])//旁边这个是他的左节点
            {
                cur->left=new TreeNode(pre[i]);
                s.push(cur);
                cur=cur->left;
            }
            else//否则是他的右节点或祖先右节点
            {
                j++;
                while(!s.empty()&&s.top()->val==vin[j])//弹出到符合的祖先
                {
                    cur=s.top();
                    s.pop();
                    j++;
                }
                cur->right=new TreeNode(pre[i]);
                cur=cur->right;
            }
        }
        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
30
31
32
33

时间复杂度:O(n)遍历数组一次，弹出栈最多n次
空间复杂度:O(n)，栈空间最大为n

二、 输出二叉树的右视图

解法一:递归建树+dfs(推荐)

• 检查两遍历序列的大小，若为0，返回NULL
• 建树，每次利用前序遍历第一个元素为根节点，在中序遍历中找到该节点并划分左右子树，分割数组递归建树
• dfs打印右视图时使用哈希表存储每个深度对应的最右边节点，初始化两个栈辅助遍历，一个记录dfs时的节点，另一个记录深度，根节点先入栈
• 对每个访问节点，左子节点先进栈，右子节点后进，由栈的性质，出栈时右边先被访问，
• 当哈希表该层无元素时，添加的第一个该层遇到的节点即为最右节点
• 使用一个变量逐层维护深度最大值，最后遍历深度，从哈希表中读出每个深度的最右节点加入数组

class Solution {
public:
    //四个int类数据分别代表先序最左下标，中序最左下标，先序最右下标，中序最右下标
    TreeNode*buildTree(vector<int>&pre,vector<int>&vin,int l1,int l2,int r1,int r2)
    {
        if(l1>r1||l2>r2)
            return NULL;
        TreeNode*root=new TreeNode(pre[l1]);
        int vin_root_index=0;//保存根节点在中序遍历数组里的下标
        for(int i=l2;i<=r2;i++)
        {
            if(vin[i]==pre[l1])
            {
                vin_root_index=i;
                break;
            }
        }
        int leftsize=vin_root_index-l2,//左子树大小
        rightsize=r2-vin_root_index;//右子树大小
        //递归构建子树
        root->left=buildTree(pre, vin, l1+1,l2 ,l1+leftsize, l2+leftsize-1);
        root->right=buildTree(pre, vin, r1-rightsize+1, vin_root_index+1, r1, r2);
        return root;
    }
    vector<int>dfs(TreeNode*root)
    {
        unordered_map<int, int>m;//右边为最深处的值
        int max_depth=-1;//记录最大深度
        stack<TreeNode*>nodes;//维护深度访问的节点
        stack<int>depths;//维护dfs时的深度
        nodes.push(root);
        depths.push(0);
        while(!nodes.empty())
        {
            TreeNode*node=nodes.top();
            nodes.pop();
            int depth=depths.top();
            depths.pop();
            if(node!=NULL)
            {
                max_depth=max(depth,max_depth);
                if(m.find(depth)==m.end())//不存在时插入节点
                    m[depth]=node->val;
                nodes.push(node->left);
                nodes.push(node->right);
                depths.push(depth+1);
                depths.push(depth+1);
            }
        }
        vector<int>tmp;
        for(int i=0;i<=max_depth;i++)
            tmp.push_back(m[i]);
        return tmp;
    }
    vector<int> solve(vector<int>& pre, vector<int>& vin) {
        // write code here
        vector<int>tmp;
        if(pre.size()==0)
            return tmp;
        TreeNode*root=buildTree(pre,vin, 0, 0, pre.size()-1, vin.size()-1);
        //每层返回最右节点
        return dfs(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

时间复杂度:O(n^2),建树递归O(n),中序遍历循环查找O(n),dfsO(n),为O( n ^2)
空间复杂度:递归栈，哈希表，栈的空间都为O(n)

解法二:哈希表优化的递归建树+层序遍历

• 检查遍历数组大小
• 遍历前序数组，用哈希表将中序遍历中的数值与前序遍历的下标建立映射
• 按照解法一递归划分子树，不过可以利用哈希表直接在中序遍历数组中找到根节点的位置
• 建立队列辅助层次遍历
• 用一个变量记录当前队列大小，当变量值为0时即到达最右，记录该节点元素

class Solution {
public:
    unordered_map<int,int>index;
    TreeNode*buildTree(vector<int>&pre,vector<int>&vin,int l1,int r1,int l2,int r2)
    {
        if(l1>r1||l2>r2)
            return NULL;
        int pre_root=l1;//前序遍历第一个节点为根节点
        int vin_root=index[pre[pre_root]];//中序遍历里定位根节点
        TreeNode*root=new TreeNode(pre[pre_root]);
        int leftsize=vin_root-l2;//左子树节点数
        root->left=buildTree(pre, vin, l1+1, l1+leftsize, l2,vin_root-1);
        root->right=buildTree(pre, vin, l1+leftsize+1, r1, vin_root+1, r2);
        return root;
    }
    vector<int>dfs(TreeNode*root)
    {
        vector<int>v;
        queue<TreeNode*>q;
        q.push(root);
        while(!q.empty())
        {
            int size=q.size();//记录该层节点数
            while(size--)
            {
                TreeNode*tmp=q.front();
                q.pop();
                if(tmp->left)
                    q.push(tmp->left);
                if(tmp->right)
                    q.push(tmp->right);
                if(size==0)//最右元素
                    v.push_back(tmp->val);
            }
        }
        return v;
    }
    vector<int> solve(vector<int>&pre, vector<int>&vin) {
        // write code here
        vector<int>tmp;
        if(pre.size()==0)
            return tmp;
        for(int i=0;i<pre.size();i++)
            index[vin[i]]=i;
        TreeNode*root=buildTree(pre, vin, 0, pre.size()-1, 0, vin.size()-1);
        return dfs(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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

时间复杂度:O(n)，其中n为二叉树节点个数，每个节点访问一次，哈希表直接访问数组中的元素
空间复杂度:O(n)，递归栈深度、哈希表、队列的空间都为O(n)