lc

题目：二叉树的右视图 middle 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

 

package leetCode.BFS; import java.util.ArrayDeque; import java.util.LinkedList; import java.util.List; public class lc_bfs_199_rightSideView { /* 题目：二叉树的右视图 middle 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- */ /* 思路： 1.bfs(最容易想到) 2.dfs(这个很妙) */ public List<Integer> rightSideView(TreeNode root) { LinkedList<Integer> ans = new LinkedList<>(); if (root == null) return ans; ArrayDeque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { int count = queue.size(); for (int i = 0; i < count; i++) { TreeNode curNode = queue.poll(); if (curNode.left != null) queue.add(curNode.left); if (curNode.right != null) queue.offer(curNode.right); if (i == count - 1) { ans.add(curNode.val); } } } return ans; } /** * 思路： 我们按照 「根结点 -> 右子树 -> 左子树」 的顺序访问， * 就可以保证每层都是最先访问最右边的节点的。 * （与先序遍历 「根结点 -> 左子树 -> 右子树」正好相反，先序遍历每层最先访问的是最左边的节点） * */ public List<Integer> rightSideView2(TreeNode root) { LinkedList<Integer> ans = new LinkedList<>(); dfs(root,ans, 1);// 从根节点开始访问，根节点深度是1 return ans; } public void dfs(TreeNode node, List<Integer> list, int depth) { if (node == null) return; // 先访问 当前节点，再递归地访问 右子树 和 左子树。 // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点， // 因此将当前节点加入res中。 if (depth > list.size()) list.add(node.val); dfs(node.right, list,depth + 1); dfs(node.left,list, depth + 1); } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } }