MUYANG GUO / INDEX

LeetCode

LeetCode 95 Unique Binary Search Trees II - Medium

95. Unique Binary Search Trees II -- Medium

·1 min read·#LeetCode#Medium#Python

95. Unique Binary Search Trees II — Medium

Open on LeetCode

Problem

  1. Unique Binary Search Trees II -- Medium

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

Example:

Input: 3 Output: [ [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 BST's shown below:

1 3 3 2 1 \ / / / \
3 2 1 1 3 2 / / \
2 1 2 3

Constraints:

0 <= n <= 8

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        # write your code here
        if n == 0:
            return
        return self.dfs(1, n)
        
    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):
            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:
                for j in RightTree:
                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res

Comments