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>();
    	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
    			if (node.left != null)
    			if (node.right != null)
    	return res;

Log in to reply

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