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.
Example:
Input: [1,2,3,null,5,null,4] Output: [1, 3, 4] Explanation: 1 <--- / \ 2 3 <--- \ \ 5 4 <--- |
- Perform a breath first traversal of the tree also called a level order traversal.
- Before you start processing any level, add the last node from your Q/list to the return list. That’s the node the user would see from the right side.
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> ret = new ArrayList<Integer>(); LinkedList<TreeNode> q = new LinkedList<TreeNode>(); if ( root != null ) q.add(root); while ( q.size() > 0 ) { int levelSize = q.size(); ret.add(q.getLast().val); for ( int i = 0 ; i < levelSize ; i++ ) { TreeNode curr = q.remove(0); if ( curr.left != null ) q.add(curr.left); if ( curr.right != null ) q.add(curr.right); } } return ret; } } |
