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,

Screen Shot 2016-04-11 at 7.48.50 PM.png

You should return [1, 3, 4].

Solution 1: BFS

public class Solution {
    /*
     * Queue class: 
     * add nodes: add() or offer(); 
     * pop nodes: poll() 
     */
    public List<Integer> rightSideView(TreeNode root) {
        //list is used to store the reture value 
        List<Integer> list = new LinkedList<Integer>();
        if (root == null)  {
            return list; 
        }
        //Queue is used to store nodes when traversing the tree
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); 
        queue.offer(root);
        TreeNode node = null; 
        while (!queue.isEmpty()) {
            /* we need to know the size of the queue since we have 
             * to consider the childs of each layer of nodes, and 
             * get the right child of the most-right child of a layer.
             */
            int size = queue.size(); 
            for (int i = 0; i< size; i++) {
                //the for-loop enables us to get the node from left to right
                node = queue.poll(); 
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            list.add(node.val);
        }
        return list; 
    }
}

Solution 2: DFS


public class Solution {
    /*
     * Queue class: 
     * add nodes: add() or offer(); 
     * pop nodes: poll() 
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>(); 
        if (root == null) {
            return list; 
        }
        helper (root, list, 0); 
        return list; 
    }
    
    private void helper (TreeNode root, List<Integer> list, int insertPosition){
        if (insertPosition == list.size()) {
            list.add(root.val);
        }
        if (root.right != null) {
            helper(root.right, list, insertPosition + 1); 
        }
        if (root.left != null) {
            helper(root.left, list, insertPosition + 1); 
        }
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s