Binary Tree Right Side View

描述

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example, given the following binary tree,

  1.    1            <---
  2.  /   \
  3. 2     3         <---
  4.  \     \
  5.   5     4       <---

You should return [1, 3, 4].

分析

层次遍历。

代码

  1. // Binary Tree Right Side View
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<Integer> rightSideView(TreeNode root) {
  5.         List<Integer> result = new ArrayList<>();
  6.         Queue<TreeNode> current = new LinkedList<>();
  7.         Queue<TreeNode> next = new LinkedList<>();
  9.         if(root == null) {
  10.             return result;
  11.         } else {
  12.             current.offer(root);
  13.         }
  15.         while (!current.isEmpty()) {
  16.             ArrayList<Integer> level = new ArrayList<>(); // elments in one level
  17.             while (!current.isEmpty()) {
  18.                 TreeNode node = current.poll();
  19.                 level.add(node.val);
  20.                 if (node.left != null) next.add(node.left);
  21.                 if (node.right != null) next.add(node.right);
  22.             }
  23.             result.add(level.get(level.size()-1));
  24.             // swap
  25.             Queue<TreeNode> tmp = current;
  26.             current = next;
  27.             next = tmp;
  28.         }
  29.         return result;
  30.     }
  31. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/binary-tree-right-side-view.html