Dead simple java iterative solution with detailed explanation


  • 0
    F

    Tradition BFS offers at most 2 nodes to a queue in the while-loop (i.e. the children of a current node that has been polled):

    public void bfs(TreeNode root) {
    	if (root == null) return;
    	Queue<TreeNode> queue = new LinkedList<TreeNode>();
    	queue.offer(root);
    	while (!queue.isEmpty()) {
    		// at most 1 node polled from queue
    		TreeNode node = queue.poll();
    
    		// at most 2 nodes offered to queue
    		if (node.left != null) queue.offer(node.left);
    		if (node.right != null) queue.offer(node.right);
    	}
    }
    

    This can be slightly re-written so that all nodes in the queue are polled, and their children are offered to the queue:

    public void bfs_v2(TreeNode root) {
    	if (root == null) return;
    	Queue<TreeNode> queue = new LinkedList<TreeNode>();
    	queue.offer(root);
    	while (!queue.isEmpty()) {			
    		int size = queue.size();
    		// loop over all existing nodes in queue
    		for (int i = 0; i < size; i++) {
    			// at most 1 node polled from queue PER ITERATION
    			TreeNode node = queue.poll();
    
    			// at most 2 nodes offered to queue PER ITERATION
    			if (node.left != null) queue.offer(node.left);
    			if (node.right != null) queue.offer(node.right);
    		}
    	}
    }
    

    If you have made it this far, it's easy to see that finding the "right-most" node within the for-loop is simple: it's the element at the "size - 1" index. So, you can modify the above code gently to get your answer

    public List<Integer> rightSideView(TreeNode root) {
    
    	List<Integer> views = new ArrayList<Integer>(); // result list
            if (root == null) return;
    	Queue<TreeNode> queue = new LinkedList<TreeNode>();
    	queue.offer(root);
    	while (!queue.isEmpty()) {			
    		int size = queue.size();
    		// loop over all existing nodes in queue
    		for (int i = 0; i < size; i++) {
    			// at most 1 node polled from queue PER ITERATION
    			TreeNode node = queue.poll();
                            if (i == size - 1) views.add(node.val); // money-shot!
    			// at most 2 nodes offered to queue PER ITERATION
    			if (node.left != null) queue.offer(node.left);
    			if (node.right != null) queue.offer(node.right);
    		}
    	}
            return views;
    }
    

Log in to reply
 

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