力扣199. 二叉树的右视图（DFS，BFS）

Problem: 199. 二叉树的右视图

文章目录

题目描述
思路
解题方法
复杂度
Code

题目描述

思路

无论是DFS还是BFS我们都要思考到达二叉树的每一层（或者每一层中的每一个节点）时，我们都该如何按题目要求做出对应得处理!!!在本体中我们主要是：

1.当右子树与左子树等高或者右子树高于左子树时，我们只添加每一个右子树得右节点到结果集（根节点得左子树整个都去除）
2.当左子树高于右子树时，我们将等高得部分按1中处理，左子树高出右子树得部分，再将其右子树得右节点添加到结果集

解题方法

思路1：DFS

1.创建unordered_map<int, int> rightmostValueAtDepth;记录每一层应该添加到右视图的节点，int maxDepth = -1;记录并维护当前的最大深度，stack<TreeNode > nodeStack;用于DFS过程中的存储节点，stack depthStack;用于同时记录DFS过程中的树的深度；
2.将根节点添加到nodeStack中，while循环遍历（循环退出条件为nodeStack为空），每次弹出nodeStack和depthStack中的栈顶元素node与depth，若此时node不为空则更新最大深度，同时若rightmostValueAtDepth[depth]不存在则添加到rightmostValueAtDepth中*；并且将node -> left;node -> right；depth + 1;depth + 1分别添加到对应的nodeStack和depthStack栈
3.最后将rightmostValueAtDepth中的值添加到一个一维数组中即可

思路2：BFS
大体实现直接套用BFS代码的模板书写即可，具体解释下面代码实现中的两个点

1.由于常规的BFS模板均是先添加左子树节点到队列，再添加右子树节点到队列所以我们可以利用数组元素可以覆盖的特性在每次添加节点到队列时，也将该节点值放入一个空间大小为1的数组temp中，这样操作后无论是思路中1、2哪种情况，都能保证最后添加到结果集中的节点值是复合题目右视图这个定义；
2.按常规BFS代码的实现（或者说就是按下面代码前面部分的操作）会导致最后一个被写到temp数组中的元素会添加两次到最终的结果集中，所以要push_back一次!!!

复杂度

思路1、2均如下
时间复杂度:

$O (n)$

空间复杂度:

$O (n)$

Code

思路1：

class Solution {
public:
    /**
     * DFS
     *
     * @param root The root of a binary tree
     * @return vector<int>
     */
    vector<int> rightSideView(TreeNode *root) {
        if (root == nullptr) {
            return {};
        }
        unordered_map<int, int> rightmostValueAtDepth;
        int maxDepth = -1;
        stack<TreeNode *> nodeStack;
        stack<int> depthStack;
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.empty()) {
            TreeNode *node = nodeStack.top();
            nodeStack.pop();
            int depth = depthStack.top();
            depthStack.pop();

            if (node != nullptr) {
                //Maintain the maximum depth of a binary tree
                maxDepth = max(maxDepth, depth);
                //If not in the map collection, add it
                if (rightmostValueAtDepth.find(maxDepth) == rightmostValueAtDepth.end()) {
                    rightmostValueAtDepth[depth] = node->val;
                }
                nodeStack.push(node->left);
                nodeStack.push(node->right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }
        vector<int> res;
        for (int i = 0; i < maxDepth; ++i) {
            res.push_back(rightmostValueAtDepth[i]);
        }
        return res;
    }
};

思路2：

class Solution {
public:
    /**
     * BFS
     * 
     * @param root The root of a binary tree
     * @return vector<int>
     */
    vector<int> rightSideView(TreeNode* root) {
        if (root == nullptr) {
            return {};
        }
        if (root -> left == nullptr && root -> right == nullptr) {
            return {root -> val};
        }
        vector<int> res;
        vector<int> temp(1);
        queue<TreeNode*> queue;
        res.push_back(root -> val);
        queue.push(root);
        while (!queue.empty()) {
            int curLevelSize = queue.size();
            for (int i = 0; i < curLevelSize; ++i) {
                TreeNode* curLevelNode = queue.front();
                queue.pop();
                if (curLevelNode -> left != nullptr) {
                    temp[0] = curLevelNode -> left -> val;
                    queue.push(curLevelNode -> left);
                }
                if (curLevelNode -> right != nullptr) {
                    temp[0] = curLevelNode -> right -> val;
                    queue.push(curLevelNode -> right);
                }
            }
            res.push_back(temp[0]);
        }
        //Pop the last repetitive node
        res.pop_back();
        return res;
    }
};