题目描述

给定一个整数 n, 生成所有由 1 ... n 为节点所组成的二叉搜索树. 此题是96题的延续, 在计算可能的二叉搜索树个数的基础上, 增加了一点难度, 要求构造出全部的二叉搜索树.

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
# 表示层次遍历的结果

解题思路

当n=10时, 全部的二叉搜索树按照根节点的情况可以分成1, 2, 3, ... , 10共10类. 以根节点为4为例, 首先需要计算出以[1, 2, 3]为节点的全部二叉搜索树lefts, 然后计算出以[5, 6, 7, 8, 9, 10]为节点的全部二叉搜索树rights, 最后用两层循环取出lefts和rights中的元素, 构造以4为根节点的二叉搜索树, 根节点取其他值时同理. 其中计算左右子树的过程可以用递归实现, 还是要注意递归函数的出口哦.

代码实现

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n <= 0:
            return []
        res = self.generateTrees0(1, n)
        return res

    def generateTrees0(self, a: int, b: int) -> List[TreeNode]:
        # 递归出口
        if a > b:
            return [None]
        if a == b:
            res = [TreeNode(a)]
            return res
        res = []
        for mid in range(a, b+1):
            left = self.generateTrees0(a, mid-1)
            right = self.generateTrees0(mid+1, b)
            for i in range(len(left)):
                for j in range(len(right)):
                    root = TreeNode(mid)
                    root.left = left[i]
                    root.right = right[j]
                    res.append(root)
        return res

更多leetcode题解敬请期待。