96.md

题目地址

https://leetcode-cn.com/problems/unique-binary-search-trees/

解答1

class Solution:
    def numTrees(self, n: int) -> int:
        """
            不同的二叉搜索树(非最优解, 卡特兰公式)

            给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
            输入: 3
            输出: 5
            解释:
            给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

            构造二叉搜索树:
            1. nums里取一个元素作为根
            2. 遍历其他元素, 插入树, 根据不同的插入位置递归

        """
        dp = [0 for _ in range(n + 1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - j - 1]

        return dp[-1]

解答2

class Solution:
    def numTrees(self, n: int) -> int:
        """
            不同的二叉搜索树(非最优解, 卡特兰公式)

            给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
            输入: 3
            输出: 5
            解释:
            给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

            构造二叉搜索树:
            1. nums里取一个元素作为根
            2. 遍历其他元素, 插入树, 根据不同的插入位置递归

        """

        def factorial(n):
            return 1 if n == 0 else n * factorial(n - 1)

        return factorial(2 * n) // (factorial(n + 1) * factorial(n))

解答3

class Solution:
    def numTrees(self, n: int) -> int:
        """
            不同的二叉搜索树(递归缓存)

            给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
            输入: 3
            输出: 5
            解释:
            给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

            构造二叉搜索树:
            1. nums里取一个元素作为根
            2. 遍历其他元素, 插入树, 根据不同的插入位置递归
        """
        cache = [-1 for _ in range(n + 1)]
        return self.countTrees(n, cache)

    def countTrees(self, n, cache):
        if n == 0:
            return 1
        if n == 1:
            return 1

        if cache[n] != -1:  # -1 means we don't know countTrees(n) yet.
            return cache[n]

        Result = 0
        for i in range(n):
            LeftTrees = self.countTrees(i, cache)
            RightTrees = self.countTrees(n - i - 1, cache)
            Result += LeftTrees * RightTrees
        cache[n] = Result
        return Result

构造方法

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data
        self.left_child = None
        self.right_child = None


def constructBinaryTree(inorder_traversal, left_index, right_index):
    """
        不同的二叉搜索树(构造出全部)

        给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
        输入: 3
        输出: 5
        解释:
        给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

        构造二叉搜索树:
        1. nums里取一个元素作为根
        2. 遍历其他元素, 插入树, 根据不同的插入位置递归
    """
    if left_index > right_index:  # 二叉树为空树，直接返回空根节点
        return [BinaryTreeNode(None)]

    if left_index == right_index:  # 二叉树仅含一个节点必然为二叉搜索树
        root = BinaryTreeNode(inorder_traversal[left_index])
        return [root]

    root_node_list = []  # 当前中序序列对应的所有二叉树的根节点表
    for i in range(left_index, right_index + 1):
        left_sub = constructBinaryTree(inorder_traversal, left_index, i - 1)  # 构造所有左子树
        right_sub = constructBinaryTree(inorder_traversal, i + 1, right_index)  # 构造所有右子树
        for j in range(len(left_sub)):
            for k in range(len(right_sub)):  # 由构造出的左右子树合成当前中序序列对应的所有二叉树
                root = BinaryTreeNode(inorder_traversal[i])
                root.left_child = left_sub[j]
                root.right_child = right_sub[k]
                root_node_list.append(root)

    return root_node_list


def isBST(root):  # 判断二叉树是否为二叉搜索树
    def helper(node, lower, upper):
        if not node or not node.data:
            return True

        if lower < node.data < upper:
            return helper(node.left_child, lower, node.data) and helper(node.right_child, node.data, upper)
        else:
            return False

    return helper(root, float('-inf'), float('inf'))


def midTraverse(root):
    """
    中序遍历
    """
    if root is None:
        return
    midTraverse(root.left_child)
    print(root.data,
          root.left_child.data if root.left_child else None,
          root.right_child.data if root.left_child else None)
    midTraverse(root.right_child)


def main():
    n = 4
    inorder_traversal = [x for x in range(1, n + 1)]
    root_list = constructBinaryTree(inorder_traversal, 0, len(inorder_traversal) - 1)

    for i in range(len(root_list)):
        result = isBST(root_list[i])
        if result is False:
            print("错误,构造出的二叉树中存在不为二叉搜索树的二叉树")
            exit(-1)

    tree_num = 1
    for m in root_list:
        midTraverse(m)
        print("-" * 20 + f"{tree_num}")
        tree_num += 1
    print(f"对应的二叉树共有{len(root_list)}棵,它们均为二叉搜索树")