怒刷 LeetCode 100 道 (95)

來自專欄編程人生

題目

Description:

Given an integer n, generate all structurally unique BSTs (binary search trees) that store values 1 ... n.

Example:

Input: 3Output:[ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3]]Explanation:The above output corresponds to the 5 unique BSTs shown below: 1 3 3 2 1 / / / 3 2 1 1 3 2 / / 2 1 2 3

解法

# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution: def generateTrees(self, n): """ :type n: int :rtype: List[TreeNode] """ if n == 0: return [] ret = [[[] for i in range(n+1)] for j in range(n+1)] self.get_return(1,n,ret) return self.get_return(1, n, ret) def get_return(self, index, n, ret): if index > n: return [None] if index == n: return [TreeNode(index)] if ret[index][n]: return ret[index][n] for i in range(index, n+1): left = self.get_return(index, i - 1, ret) right = self.get_return(i+1, n, ret) for l in left: for r in right: root = TreeNode(i) ret[index][n].append(root) root.left = l root.right = r return ret[index][n]

推薦閱讀：