199. 二叉树的右视图
难度中等 416
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <—
/
2 3 <—
\
5 4 <—
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> depthQueue = new LinkedList<Integer>();
nodeQueue.add(root);
depthQueue.add(0);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();//等价removeFirst
int depth = depthQueue.remove();
if (node != null) {
// 维护二叉树的最大深度
max_depth = Math.max(max_depth, depth);
// 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
rightmostValueAtDepth.put(depth, node.val);
nodeQueue.add(node.left);
nodeQueue.add(node.right);
depthQueue.add(depth + 1);
depthQueue.add(depth + 1);
}
}
List<Integer> rightView = new ArrayList<Integer>();
for (int depth = 0; depth <= max_depth; depth++) {// =
rightView.add(rightmostValueAtDepth.get(depth));
}
return rightView;
}BFS
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == size - 1) { //将当前层的最后一个节点放入结果列表
res.add(node.val);
}
}
}
return res;
}
作者：sweetiee
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee####
DFS
List<Integer> res = new ArrayList<>();
public List<Integer> rightSideView(TreeNode root) {
dfs(root, 0); // 从根节点开始访问，根节点深度是0
return res;
}
private void dfs(TreeNode root, int depth) {
if (root == null) {
return;
}
// 先访问 当前节点，再递归地访问 右子树 和 左子树。
if (depth == res.size()) { // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
res.add(root.val);
}
depth++;
dfs(root.right, depth);///先添加又节点,执行左节点时 不满足if depth== 条件。
dfs(root.left, depth);
}
作者：sweetiee
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee/
