LeetCode0095.UniqueBinarySearchTreesIIDifferentBinarySearchTreesII【Medium】【Python】【分而治之】【DFS】问题LeetCode给定一个整数n，生成所有结构唯一的BST's(二叉搜索树）存储值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]]解释：上面的输出对应于下面显示的5个唯一BST：13321\///\\321132//\\2123问题缩减给定一个整数n，生成所有由1...n个节点组成的二叉搜索树。示例：输入：3输出：[[1,null,3,2],[3,2,null,1],[3,1,null,null,2],[2,1,3],[1,null,2,null,3]]解释：以上输出对应以下五棵结构不同的二叉搜索树：13321\///\321132//\\2123思想分而治之递归DFS递归构造从1-n中选取一个i作为根节点，i左边的所有节点构成左子树，i右边的所有节点构成右子树。时间复杂度:$$O(\frac{4^n}{n^{1/2}})$$空间复杂度:$$O(\frac{4^n}{n^{1/2}})$$Python3代码#定义二叉树节点。#classTreeNode:#def__init__(self,x):#self.val=x#self.left=None#self.right=Noneclass解决方案：defgenerateTrees(self,n:int)->List[TreeNode]:ifn==0:return[]else:returnself.generateTreesDFS(1,n)#DFSdefgenerateTreesDFS(self,left,right):ifleft>right:返回[None]ans=[]foriinrange(left,right+1):left_nodes=self.generateTreesDFS(left,i-1)#如果选择i作为根，则所有可能的左子树right_nodes=self.generateTreesDFS(i+1,right)#如果选择i作为left_nodeinleft_nodes的根，所有可能的右子树：forright_nodeinright_nodes:root=TreeNode(i)root.left=left_noderoot.right=right_nodeans.append(root)返回ans代码地址GitHub链接
