Simple Java BFS solution O(n) time


  • 0
    C
    public void connect(TreeLinkNode root) {
        TreeLinkNode node = root;
        TreeLinkNode current = null, nextLevel = null;
        while (node != null) {
            current = node;
            nextLevel = null;
            node = null;
            while (current != null) {
                if (current.left != null) {
                    if (nextLevel == null) {
                        nextLevel = current.left;
                        node = nextLevel;
                    } else {
                        nextLevel.next = current.left;
                        nextLevel = nextLevel.next;
                    }
                }
                if (current.right != null) {
                    if (nextLevel == null) {
                        nextLevel = current.right;
                        node = nextLevel;
                    } else {
                        nextLevel.next = current.right;
                        nextLevel = nextLevel.next;
                    }
                }
                current = current.next;
            }
        }
    }

  • 0
    L

    The problem requires us to solve it with constant extra space while you use a O(n) space queue.


  • 0
    C

    Thanks for your reminder, I will rewrite my code with constant extra space.


Log in to reply
 

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