【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;
}
};
六.题目总结
重点还是思想
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码