My AC python recursive solution


  • 0
    X

    The basic idea is to first flat left sub-tree and return the last node, then flat the right sub-tree and return the last node, at last move flattened left sub-tree to root.right and append flattened the right sub-tree to the last node of flattened left sub-tree. The base case is a little messy, might someone know how to write more concise code ?

    # 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 recursive(self,root):
            if(root == None):
                return root
            if(root.left == None and root.right == None):
                return root
            
            leftTail, rightTail = None, None
            if(root.right != None):
                rightTail = self.recursive(root.right)
            if(root.left != None):
                leftTail = self.recursive(root.left)
                tmp = root.right
                root.right = root.left
                leftTail.right = tmp
                root.left = None
                if(rightTail == None):
                    rightTail = leftTail
            return rightTail
                
        def flatten(self, root):
            """
            :type root: TreeNode
            :rtype: void Do not return anything, modify root in-place instead.
            """
            self.recursive(root)
            
            
    

Log in to reply
 

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