【LeetCode热题100】199. 二叉树的右视图（二叉树）

一.题目要求

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

二.题目难度

中等

三.输入样例

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:
输入: [1,null,3]
输出: [1,3]

示例 3:
输入: []
输出: []

提示:
二叉树的节点个数的范围是 [0,100]
-100 <= Node.val <= 100

四.解题思路

解法1.层序遍历，每一层最后一个结点值加入结果
解法2.DFS递归，方法来自 https://www.bilibili.com/video/BV18M411z7bb

五.代码实现

解1

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {

        if(!root) return {};
        vector<int> ans;
        queue<TreeNode*> sup;
        sup.push(root);
        TreeNode* p = sup.front();
        while(!sup.empty())
        {
            int size = sup.size();
            while(size > 0)
            {
                size--;
                if(!size) ans.push_back(p->val);
                sup.pop();
                if(p->left) sup.push(p->left);
                if(p->right) sup.push(p->right);
                p = sup.front();
            }          
        }
        return ans;
    }
};

解2

class Solution {
    vector<int> ans;

    void dfs(TreeNode *node, int depth) {
        if (node == nullptr) return;
        if (depth == ans.size())
            ans.push_back(node->val);
        dfs(node->right, depth + 1);
        dfs(node->left, depth + 1);
    }

public:
    vector<int> rightSideView(TreeNode *root) {
        dfs(root, 0);
        return ans;
    }
};

六.题目总结

重点还是思想