P229 二叉树的右视图

描述#

这个题目说的是，给你一棵二叉树，并且你站在这棵树的右边，你要返回从上到下看到的节点值。

比如说，给你的二叉树是：
 1

/   

2     4
/ 

6   8
站在这棵二叉树的右边看过来，从上到下看到的数字依次是：
[1, 4, 8]

相关视频：二叉树的层序遍历

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public List<Integer> rightSideViewBFS(TreeNode root) {
    if (root == null) return Collections.emptyList();
    List<Integer> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);

    while (!q.isEmpty()) {
      result.add(q.peek().val);
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode node = q.poll();
        if (node.right != null) q.add(node.right);
        if (node.left != null) q.add(node.left);
      }
    }
    return result;
  }

  private void dfs(TreeNode root, List<Integer> result, int level) {
    if (root == null) return;
    if (level == result.size()) result.add(root.val);
    dfs(root.right, result, level+1);
    dfs(root.left, result, level+1);
  }

  // Time: O(n), Space: O(n)
  public List<Integer> rightSideViewDFS(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfs(root, result, 0);
    return result;
  }

}