categories: [Blog,Algorithm,mid]

199. 二叉树的右视图

难度中等416
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:
1 <—-
/ \
2 3 <—-
\ \
5 4 <—-

  1. public List<Integer> rightSideView(TreeNode root) {
  2.         Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
  3.         int max_depth = -1;
  5.         Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
  6.         Queue<Integer> depthQueue = new LinkedList<Integer>();
  7.         nodeQueue.add(root);
  8.         depthQueue.add(0);
  10.         while (!nodeQueue.isEmpty()) {
  11.             TreeNode node = nodeQueue.remove();//等价removeFirst
  12.             int     depth = depthQueue.remove();
  14.             if (node != null) {
  15.                 // 维护二叉树的最大深度
  16.                 max_depth = Math.max(max_depth, depth);
  18.                 // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
  19.                 rightmostValueAtDepth.put(depth, node.val);
  21.                 nodeQueue.add(node.left);
  22.                 nodeQueue.add(node.right);
  23.                 depthQueue.add(depth + 1);
  24.                 depthQueue.add(depth + 1);
  25.             }
  26.         }
  28.         List<Integer> rightView = new ArrayList<Integer>();
  29.         for (int depth = 0; depth <= max_depth; depth++) {// = 
  30.             rightView.add(rightmostValueAtDepth.get(depth));
  31.         }
  33.         return rightView;
  34.     }

BFS

  1. public List<Integer> rightSideView(TreeNode root) {
  2.         List<Integer> res = new ArrayList<>();
  3.         if (root == null) {
  4.             return res;
  5.         }
  6.         Queue<TreeNode> queue = new LinkedList<>();
  7.         queue.offer(root);
  8.         while (!queue.isEmpty()) {
  9.             int size = queue.size();
  10.             for (int i = 0; i < size; i++) {
  11.                 TreeNode node = queue.poll();
  12.                 if (node.left != null) {
  13.                     queue.offer(node.left);
  14.                 }
  15.                 if (node.right != null) {
  16.                     queue.offer(node.right);
  17.                 }
  18.                 if (i == size - 1) {  //将当前层的最后一个节点放入结果列表
  19.                     res.add(node.val);
  20.                 }
  21.             }
  22.         }
  23.         return res;
  24.     }
  26. 作者：sweetiee
  27. 链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee

DFS

  1.     List<Integer> res = new ArrayList<>();
  3.     public List<Integer> rightSideView(TreeNode root) {
  4.         dfs(root, 0); // 从根节点开始访问，根节点深度是0
  5.         return res;
  6.     }
  8.     private void dfs(TreeNode root, int depth) {
  9.         if (root == null) {
  10.             return;
  11.         }
  12.         // 先访问 当前节点，再递归地访问 右子树 和 左子树。
  13.         if (depth == res.size()) { // 如果当前节点所在深度还没有出现在res里，说明在该深度下当前节点是第一个被访问的节点，因此将当前节点加入res中。
  14.             res.add(root.val);
  15.         }
  16.         depth++;
  17.         dfs(root.right, depth);///先添加又节点,执行左节点时 不满足if depth== 条件。
  18.         dfs(root.left, depth);
  19.     }
  21. 作者：sweetiee
  22. 链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/solution/jian-dan-bfsdfs-bi-xu-miao-dong-by-sweetiee/