每日一练：二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

一、题目要求

给定一个二叉树的 根节点 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-层序遍历 O(N)

        这个题可以用层序遍历来完成，但是方向是从右向左进行，只将每层的第一个节点放入数组中。

class Solution {
public:vector<int> rightSideView(TreeNode* root) {vector<int> ret;queue<TreeNode*> q1;q1.push(root);while(!q1.empty()){queue<TreeNode*> q2;int oldLen = ret.size();while(!q1.empty()){root = q1.front();q1.pop();if(root != nullptr){q2.push(root->right);q2.push(root->left);if(ret.size() == oldLen)ret.push_back(root->val);}}q1 = q2;}return ret;}
};

三、解法2-递归 O(N)

        从最右路径遍历，然后遍历次右路径，最后遍历最左路径，如果某条路径比它所有右边路径中的最长路径还要长，那么多出来的节点就是右视图能看见的，将其加入结果中。

class Solution {
public:void _rightSideView(TreeNode* root,int deep){if(root == nullptr)return;if(deep > maxDeep) // 当前深度比左边路径的最长路径还要深{maxDeep = deep; // 更新最大深度ret.push_back(root->val); // 将当前节点加入结果}_rightSideView(root->right,deep+1); // 先遍历右路径_rightSideView(root->left,deep+1);  // 后遍历左路径}vector<int> rightSideView(TreeNode* root) {_rightSideView(root,1);return ret;}
private:int maxDeep = 0; // 最大深度vector<int> ret;
};

        递归的迭代版本：

class Solution {
public:vector<int> rightSideView(TreeNode* root) {stack<pair<TreeNode*, int>> s; // 存储节点和节点的当前深度s.push({root, 1});int maxDeep = 0; // 最大深度vector<int> ret;while (!s.empty()) {if (s.top().first) {root = s.top().first;int deep = s.top().second;s.pop();if (root != nullptr) {if (deep > maxDeep) {maxDeep = deep;ret.push_back(root->val);}s.push({root->left, deep + 1});s.push({root->right, deep + 1});}}elses.pop();}return ret;}
};