Java solution with queue


  • 2
    J
        public void connect(TreeLinkNode root) {
            Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
            if(root != null) q.offer(root);
            TreeLinkNode top = null, pre = null;
            while(!q.isEmpty()){
                int size = q.size();
                for(int i = 0; i < size; i++){
                    top = q.poll();
                    if(top.left != null) q.offer(top.left);
                    if(top.right != null) q.offer(top.right);
                    
                    if(i == 0) pre = top;
                    else{
                        pre.next = top;
                        pre = top;
                        }
                    if(i == size - 1) top.next = null;
                }
            }
        }

  • 0
    R

    Nice solution, but this would probably violate the "you can only use constant space" restriction, since the size of your queue at the deepest level will be proportional to the size/depth of your tree.


  • 0
    J

    @rmn Thanks. I forgot to consider it.


Log in to reply
 

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