BFS trick can be used for both Populating Next Right Pointers I/II


  • 0

    Addnullat the end of each level, if q.poll() == null but !q.isEmpty(), we add null since we are not reaching the last level. This trick can deal with any kind of binary Tree.

    public class Solution{
        public void connect(TreeLinkNode root) {
            if(root == null)    return;
            Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
            q.add(root);
            q.add(null);
            while(!q.isEmpty()){
                TreeLinkNode cur = q.poll();
                if(cur != null){
                    cur.next = q.peek();
                    if(cur.left != null)
                        q.add(cur.left);
                    if(cur.right != null)
                        q.add(cur.right);
                }else{
                    if(!q.isEmpty()) q.add(null);
                }
            }
            return;
        }
    }
    

Log in to reply
 

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