一、题目
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
二、示例
2.1> 示例 1:
【输入】 [1,2,3,null,5,null,4]
【输出】 [1,3,4]
2.2> 示例 2:
【输入】 [1,null,3]
【输出】 [1,3]
2.3> 示例 3:
【输入】 []
【输出】 []
提示:
- 二叉树的节点个数的范围是
[0,100] -
-100<= Node.val <=100
三、解题思路
根据题目描述，我们要构建一个给定二叉树的右侧视图。即，假设我们站在整棵二叉树的最右侧，向二叉树看去，能看到的每层一个节点分别是什么。那么也可以将其理解为，求解出每一层节点中最右侧的那个节点。那么针对这道题，我们可以采用两种常见的解题方式，即：层序遍历和深度优先遍历。那么层序遍历我们在之前的图解中介绍过了，核心解题思路就是两点：
【思路1】创建
Deque双向队列结构，来暂存节点。
【思路2】每次遍历前，都要先获取Deque中节点的个数num，表示某层所存在的节点个数，然后只遍历num个节点。
然后获取每层最后一个节点存储到ArrayList中即可。此处就不赘述了。
那么除了层序遍历，我们也可以采用深度优先遍历方式进行题解。那么主要的解题思路也是有两点：
【思路1】针对每次递归调用都传入
level层号；
【思路2】通过ArrayList的size()是否等于level，来判断某一层是否找到了右视图节点；如果等于，则表示之前没有找到右视图节点，然后调用add方法将当前节点保存到ArrayList即可。
以上就是本题的解题思路，为了便于大家理解，我们以二叉树为[1,2,3,null,4]为例，看一下具体的处理过程。请见下图所示；
四、代码实现
class Solution {
List<Integer> result = new ArrayList();
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0);
return result;
}
public void dfs(TreeNode node, Integer level) {
if (node == null) return;
if (result.size() == level) result.add(node.val);
dfs(node.right, level + 1);
dfs(node.left, level + 1);
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论