Simple Java code, level order traversal, link nodes at every level.


  • 0
    J

    Not space O(1), accepted anyway. Applicable to "Populating Next Right Pointers in Each Node II"

    public void connect(TreeLinkNode root) {
    	if (root == null) return;
        Queue<TreeLinkNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
        	int qlen = q.size();
        	TreeLinkNode prev = null, cur;
        	while (qlen-- > 0) {
        		cur = q.poll();
        		if (prev != null) prev.next = cur;
        		if (cur.left != null) q.offer(cur.left);
        		if (cur.right != null) q.offer(cur.right);
        		prev = cur;
        	}
        }
    }

  • 1
    L

    It doesn't satisfy "constant extra space".


Log in to reply
 

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