Question

link

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            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

            <div id="tags" class="btn btn-xs btn-warning">Show Tags</div>
            <span class="hide">
              
              <a class="btn btn-xs btn-primary" href="/tag/tree/">Tree</a>
              
              <a class="btn btn-xs btn-primary" href="/tag/depth-first-search/">Depth-first Search</a>
              
              <a class="btn btn-xs btn-primary" href="/tag/breadth-first-search/">Breadth-first Search</a>
              
            </span>
          
        </div>

Solution

This question basically is binary tree traversal. During the process, we keep a list and update the elements in it.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        traverse(result, root, 1);
        return result;
    }

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