Accepted Java solution using two queues


  • 1
    H
    public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(root == null)return res;
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        q2.add(root);
        while(!q2.isEmpty()){
            res.add(q2.peek().val);
            q1 = new LinkedList(q2);
            q2.clear();
            while(!q1.isEmpty()){
                TreeNode cur = q1.poll();
                if(cur.right != null)q2.add(cur.right);
                if(cur.left != null)q2.add(cur.left);
            }
        }
        return res;
    }
    

    }

    The key is to do a level order traversal and print out the rightmost node at each level.
    Use each queue to take all nodes at one level then alternate.


  • 1
    C

    Why bother using two queues, you can use only two local variable to track the size of the current level and next level. When size of current level turns 0, swap them.


Log in to reply
 

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