Sharing elegant and simple Python O(1) space Iterative, beats 90%, with comments

  • 1
    class Solution(object):
        def connect(self, root):
            def get_next_node(cur):
                while cur:
                    if cur.left:
                        return cur, cur.left
                    if cur.right:
                        return cur, cur.right
                    cur =
                return None, None
            cur = root
            prev = cur
            while cur:
                # First get the next child (neighbor node in same level)
                next_node, its_child = get_next_node(
                if cur.left:
           = cur.right if cur.right else its_child
                if cur.right:
           = its_child
                # If exists a node in my level with at least one child, then
                # go there
                if next_node:
                    cur = next_node
                    # Get next node in next level
                    cur = prev.left if prev.left else prev.right
                    cur, _ = get_next_node(cur)
                    prev = cur

Log in to reply

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