A Python Recursive Solution: Divide-and-Conquer Algorithm


  • 0
    I

    It is right to deal with left subsequence or right subsequence in the same way to solve the whole problem sequence, only attention to the offet in each subsequences.

    class Solution(object):
        def generateTrees(self, n, offset=0):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            
            #Found the judger explains [None] to [[]]...
            if n == 0:
                return []
    
            res = []
            for i in range(1, n + 1):
                ls = self.generateTrees(i-1, offset) or [None]
                rs = self.generateTrees(n-i, i+offset) or [None]
                for l in ls:
                    for r in rs:
                        root = TreeNode(i + offset)
                        root.left = l
                        root.right = r
    
                        res.append(root)
    
            return res>! >! >! >! Spoiler``

Log in to reply
 

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