A Python version based on levelorder traversal - O(k) space


  • 0
    G
    # Definition for binary tree with next pointer.
    # class TreeLinkNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    #         self.next = None
    
    class Solution:
        # @param root, a tree link node
        # @return nothing
        # 12:38
        def connect(self, root):
            if not root:
                return
    
            levels = [[root]]
            self.levelConnect(root, levels)
    
        def levelConnect(self, root, levels):
            while levels:
                level = levels.pop(0)
                newLevel = []
                while level:
                    node = level.pop(0)
                    if level:
                        node.next = level[0]
                    if node.left:
                        newLevel.append(node.left)
                    if node.right:
                        newLevel.append(node.right)
    
                if newLevel:
                    levels.append(newLevel)

  • 1
    K

    I felt a BFS was much more intuitive for this problem.
    I'm not sure why the suggested method recommends DFS


Log in to reply
 

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