BFS Java solution with 2 queues


  • 1
    Q
    public class Solution {
        public void connect(TreeLinkNode root) {
            if (root == null){
                return;
            }
            Queue<TreeLinkNode> q = new ArrayDeque<TreeLinkNode>();
            Queue<TreeLinkNode> q2 = new ArrayDeque<TreeLinkNode>();
            q.add(root);
            while (!q.isEmpty()){
                TreeLinkNode n = q.poll();
                TreeLinkNode l = n.left;
                TreeLinkNode r = n.right;
                if (l!=null){
                    q2.offer(l);
                }
                if (r!=null){
                    q2.offer(r);
                }
                if (!q.isEmpty()){
                    n.next = q.peek();
                }
                else{
                    Queue<TreeLinkNode> tmp = q;
                    q = q2;
                    q2 = tmp;
                }
            }
        }
    }

  • 0
    J

    I was trying to do this recursively just as the last problem, and I find it really complicated. This is actually more straightforward.


  • 0
    A

    NOTICE::

    YOU should use constant space.


Log in to reply
 

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