题意分析

• 给出一个二叉树的前序遍历的序列和中序遍历的序列，我们需要找到这个二叉树的右视图结点的权值构成的数组。这里的右视图就是从右边向左边进行投影能看到的序列有哪些?

思路分析

• 前置知识

  • 我们首先需要知道二叉树的先序遍历的序列和中序遍历的序列是什么？

  • 如下图 我们把一棵树分为根结点，左子树和右子树。先序遍历就是先遍历序列的根节点，然后遍历序列的左子树，然后遍历序列的右子树。中序遍历就是先遍历序列的左子树，然后是根节点，最后是右子树这样的顺序。后序遍历就是先遍历序列的左子树的所有的结点，然后遍历树的右子树的所有的结点，最后遍历序列的根结点。通过以上的描述我们可以发现，其实这个先，中，后是根据遍历的根节点的顺序进行命名的。方便记忆。

  

• 我们按照很常规的思维，如果这棵二叉树，然后就是一个模板问题了。给出一个二叉树的先序和中序序列，重构这棵二叉树。我们需要使用递归的方法来实现。得到这棵二叉树的所有的结点的信息之后，我们需要使用继续思考如何得到右视图的序列，我们发现，其实我们需要找的就是每一层的最右边的序列。我们可以利用层序遍历进行处理，然后记录每一层最后出现的那个结点的权值，这个可以使用哈希表进行存储。最后从哈希表里面进行提取即可。

解法一 DFS+BFS+哈希

• 代码如下
  • 在BFS和DFS的时候需要遍历n个结点，时间复杂度为$O(n)O(n)$，哈希存储的时间复杂度也是$O(n)O(n)$，所以总的时间复杂度$O(n)O(n)$
  • 过程中利用了哈希表存储，同时使用了结构体重建n个结点，空间复杂度为$O(n)O(n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    // 构造树的每个结点
    struct node{
        node* left;
        node* right;
        int val;
    };
    // 先获取整棵树的结构
    node* create(int pL,int pR,int mL,int mR,vector<int> &xianxu, vector<int>& zhongxu){
        if(pL>pR){
            return NULL;
        }
        node* root=new node;
        root->val=xianxu[pL];
        int k;
        for(k=mL;k<=mR;k++){
            if(zhongxu[k]==xianxu[pL]){
                break;
            }
        }
        
        int numLeft=k-mL;
        // 递归左子树
        root->left=create(pL+1,pL+numLeft,mL,k-1,xianxu, zhongxu);
        // 递归右子树
        root->right=create(pL+numLeft+1,pR,k+1,mR,xianxu,zhongxu);
        
        return root;
    }
    unordered_map<int, int> mp;
    // 我们按照层序遍历这颗二叉树，然后记录每个层数最后出现的结点的权值
    void BFS(node* root){
        if(!root){
            return;
        }
        queue<pair<node*,int> > q;
        q.push(make_pair(root,1));
        mp[1]=root->val;
        while(!q.empty()){
            auto now=q.front();
            q.pop();
            // 先左子树，然后遍历右子树
            if(now.first->left){
                q.push(make_pair(now.first->left,now.second+1));
                mp[now.second+1]=now.first->left->val;
            }
            if(now.first->right){
                q.push(make_pair(now.first->right,now.second+1));
                mp[now.second+1]=now.first->right->val;
            }
        }
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        node* root=create(0,xianxu.size()-1,0,zhongxu.size(),xianxu,zhongxu);
        
        vector<int> ans;
        
        BFS(root);
        
        int n=mp.size(); // 层数
        for(int i=1;i<=n;i++){
            ans.push_back(mp[i]);
        }
        
        return ans;
    }
};

解法二 DFS

• 通过对上面的一种的解法进行求解，我们发现，其实我们在构建这棵二叉树的时候我们就是在遍历每一层，所以我们按照先遍历左子树，然后遍历右子树的顺序来进行遍历的话，我们记录到的当前这一层的最后的那个结点的权值就一定是二叉树的最右边的结点的权值了。所以可以直接省略BFS的操作，同时也没有必要在每个结点里面记录每个结点的权值。

• 代码如下

  • DFS的时候需要遍历n个结点，时间复杂度为$O(n)O(n)$，哈希存储的时间复杂度也是$O(n)O(n)$，所以总的时间复杂度$O(n)O(n)$
  • 过程中利用了哈希表存储，同时使用了结构体重建n个结点，空间复杂度为$O(n)O(n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    // 构造树的每个结点
    struct node{
        node* left;
        node* right;
    };
    // 先获取整棵树的结构
    unordered_map<int, int> mp;
    node* create(int pL,int pR,int mL,int mR,vector<int> &xianxu, vector<int>& zhongxu,int dep){
        if(pL>pR){
            return NULL;
        }
        node* root=new node;
        mp[dep]=xianxu[pL];
        int k;
        for(k=mL;k<=mR;k++){
            if(zhongxu[k]==xianxu[pL]){
                break;
            }
        }
        
        int numLeft=k-mL;
        // 递归左子树
        root->left=create(pL+1,pL+numLeft,mL,k-1,xianxu, zhongxu,dep+1);
        // 递归右子树
        root->right=create(pL+numLeft+1,pR,k+1,mR,xianxu,zhongxu,dep+1);
        
        return root;
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        node* root=create(0,xianxu.size()-1,0,zhongxu.size(),xianxu,zhongxu,1);
        
        vector<int> ans;
        
        
        int n=mp.size(); // 层数
        for(int i=1;i<=n;i++){
            ans.push_back(mp[i]);
        }
        
        return ans;
    }
};