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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
    // 建树函数
    // 四个int参数分别是前序最左节点下标，前序最右节点下标
    //                 中序最左节点下标，中序最右节点下标
    TreeNode* buildTree(vector<int>& xianxu, int l1, int r1, vector<int>& zhongxu, int l2, int r2){
        if(l1 > r1 || l2 > r2) return NULL;
        // 构建节点
        TreeNode* root = new TreeNode(xianxu[l1]);
        // 用来保存根节点在中序遍历列表的下标
        int rootIndex = 0;
        // 寻找根节点
        for(int i = 0; i < zhongxu.size(); ++i){
            if(zhongxu[i] == xianxu[l1]){
                rootIndex = i;
                break;
            }
        }
        // 左子树大小
        int leftsize = rootIndex - l2;
        // 右子树大小
        int rightsize = r2 - rootIndex;
        // 递归构建左子树和右子树
        root->left = buildTree(xianxu, l1 + 1, l1 + leftsize, zhongxu, l2, l2 + leftsize - 1);
        root->right = buildTree(xianxu, r1 - rightsize + 1, r1, zhongxu, rootIndex + 1, r2);
        return root;
    }
    // 深度优先搜索函数
    vector<int> rightSideView(TreeNode* root){
        // 右边最深处的值
        unordered_map<int, int> mp;
        // 记录最大深度
        int max_depth = -1;
        // 维护深度访问节点
        stack<TreeNode*> nodes;
        // 维护dfs时的深度
        stack<int> depths;
        
        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(max_depth, depth);
                // 如果不存在对应深度的节点我们才插入
                if(mp.find(depth) == mp.end())
                    mp[depth] = node->val;
                nodes.push(node->left);
                nodes.push(node->right);
                depths.push(depth + 1);
                depths.push(depth + 1);
            }
        }
        vector<int> res;
        for(int i = 0; i <= max_depth; ++i)
            res.push_back(mp[i]);
        return res;
    }
    vector<int> solve(vector<int>& xianxu, vector<int>& zhongxu) {
        vector<int> res;
        // 空节点
        if(xianxu.size() == 0){
            return res;
        }
        // 建树
        TreeNode* root = buildTree(xianxu, 0, xianxu.size() - 1, zhongxu, 0, zhongxu.size() - 1);
        // 找每一层最右边的节点
        return rightSideView(root);
    }
};

如果给出一个二叉树，直接输出右视图的话，层序遍历，取每层最右侧节点就好，这个题目要先根据先序遍历、中序遍历建树，建树的过程有点儿没搞懂~~~建树完成之后的深度优先搜索（dfs）也有点儿难懂~~~