Flatten Binary Tree to Linked List - Please help


  • 0
    H
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def flatten(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            if root is None:
                return root
            p = TreeNode(0)
            p.right = root
            self.flattenHelper(p, root)
        
    
    def flattenHelper(self, lastNode, node):
        lastNode.right = node
        if node.left is None and node.right is None:
            # leaf node
            lastNode = node
            return
        left = node.left
        right = node.right
        node.left = None
        node.right = None
        lastNode = node
        # reset left and right for current node
        if left is not None:
            self.flattenHelper(lastNode, left)
        if right is not None:
            self.flattenHelper(lastNode, right)
    

    for given input
    1->left = 2, 1->right = 3

    the expected result should be 1->right=2, 2->right=3

    but the above code returns 1->right=3

    I think lastNode = node has some issue but I cannot figure it out. Can someone help? Thanks!


Log in to reply
 

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