题解 | #输出二叉树的右视图#

解题思路

本质上是树的层序遍历，当然还包括了从前序中序遍历重建二叉树。
还不熟悉广度优先遍历的朋友可以先学习树的广度优先遍历和树的广度优先遍历
还不熟悉重建二叉树的朋友可以先学习重建二叉树 不过与层序遍历略有不同的是，我们只输出每层的最右侧节点值。

代码

class Solution {
public:
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        // write code here
        for(int i = zhongxu.size()-1; i >= 0; --i) pos[zhongxu[i]] = i;
        return levelSearch(buildTree(xianxu, 0, xianxu.size()-1, zhongxu, 0, zhongxu.size()-1));
    }
    
    struct TreeNode{
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int val, TreeNode* left, TreeNode* right){
            this->val = val;
            this->left = left;
            this->right = right;
        }
    };
    
    vector<int> levelSearch(TreeNode* root){
        if(!root) return {};
        vector<int> ans;
        q.push(root);
        int size = 1;
        int count = 0;
        while(!q.empty()){
            if(q.front()->left) q.push(q.front()->left);
            if(q.front()->right) q.push(q.front()->right);
            ++count;
            if(count==size){
                ans.push_back(q.front()->val);
                size = q.size()-1;
                count = 0;
            }
            q.pop();
        }
        return ans;
    }
    
    TreeNode* buildTree(const vector<int>& firstOrder, int start1, int end1, const vector<int>& secondOrder, int start2, int end2){
        if(start1>end1) return nullptr;
        if(start1==end1) return new TreeNode(firstOrder[start1],nullptr,nullptr);
        TreeNode* root = new TreeNode(firstOrder[start1],nullptr,nullptr);
        
        int i = pos[firstOrder[start1]];
        root->left = buildTree(firstOrder, start1+1, start1+i-start2, secondOrder, start2, i-1);
        root->right = buildTree(firstOrder, start1+i-start2+1, end1, secondOrder, i+1, end2);
        return root;
    }
    
    unordered_map<int, int> pos;
    queue<TreeNode*> q;
};

复杂度分析

时间复杂度： O(n)。n为二叉树节点数目不管是重建二叉树，还是层序遍历，都只需要遍历所有节点一次，所以时间复杂度为O(n)。
空间复杂度： O(n)。辅助队列和哈希表的空间消耗。