Concise JAVA solution based on BFS


  • 2

    The basic idea is using level by level BFS to traverse the tree: add the right-most node of each level to the result.

    Runtime complexity = O(n)

    n is the number of the nodes in the tree: because each node is visited only once, so the runtime complexity is O(n).

    public List<Integer> rightSideView(TreeNode root) {
    	List<Integer>res = new ArrayList<Integer>();
    	if (root == null) return res;
    	Queue<TreeNode>queue = new LinkedList<TreeNode>();
    	
    	queue.offer(root);		
    	while (!queue.isEmpty()) {//Level by level BFS 
    		int count = queue.size();
    		for (int i = 0; i < count; i++) {
    			TreeNode node = queue.poll();
    			if (i == count - 1) // The right-most node of the current level
    				res.add(node.val);
    			if (node.left != null)
    				queue.offer(node.left);
    			if (node.right != null)
    				queue.offer(node.right);
    		}
    	}
    	return res;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.