95. 不同的二叉搜索树 II

Difficulty
Medium
Tags
二叉树
二叉搜索树
URL
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
Star
❤
给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。
示例 1：
notion imagenotion image
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：
输入：n = 1
输出：[[1]]
提示：
  • 1 <= n <= 8

法1 递归

思路
二叉排序树的重要性质是，左子树上的节点值一定小于根节点，右子树上的节点值一定大于根节点。由此，可知若根节点为i，则左子树的节点为[1,...,i-1]，右子树的节点为[i+1,...,n]。可递归的构建二叉搜索树。
  1. 特判，若n==0，返回[]
  1. 定义生成树函数build_Trees(left,right)，表示生成[left,...,right]的所有可能二叉搜索树：
      • 若left>right，说明为空树，返回[None]
      • 初始化所有可能的二叉搜索树列表all_trees=[]
      • 遍历每一种可 能的节点i，遍历区间[left,right+1):
        • 所有可能的左子树列表left_trees=build_Trees(left,i−1)
        • 所有可能的右子树列表right_trees=build_Trees(i+1,right)
        • 组合所有的方式，遍历左子树列表,l：遍历右子树列表,r
          • 建立当前树节点cur_tree=TreeNode(i)
          • 将cur_tree左子树置为l
          • 将cur_tree右子树置为r
          • 将cur_tree加入树列表中
      • 返回树列表all_trees
  1. 返回build_Trees(1,n)
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

    def build_Trees(self, left, right):
        all_trees=[]
        # 这一行至关重要！！
        if(left>right):
            return [None]
        # 以 i 为根节点
        for i in range(left,right+1):
            left_trees = self.build_Trees(left, i-1)
            right_trees = self.build_Trees(i+1, right)
						# 遍历所有的可能节点
            for l in left_trees:
                for r in right_trees:
                    cur_tree=TreeNode(i)
                    cur_tree.left = l
                    cur_tree.right = r
                    all_trees.append(cur_tree)
        return all_trees