目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个整数 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]
]
解释：
以上的输出对应以下 5 种不同结构的二叉搜索树：

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

提示：

0 <= n <= 8

二、解题思路

如果将 i 作为根节点，那么 [1, i) 为的左子树节点，(i, n] n为右子树节点。

那么我们需要求左子树 [1,i)的所有排列和右子树(i, n]的所有排列。

三、代码

  

   

    

     

    
    

     

      # 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
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 def __repr__(self):
     
    
   

    

     

    
    

     
 return str(self.val)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def generateTrees(self, n: int) -> list:
     
    
   

    

     

    
    

     

       res = []
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 if n < 1:
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 def dfs(st, end):
     
    
   

    

     

    
    

     

       res = []
     
    
   

    

     

    
    

     
 if st > end:
     
    
   

    

     

    
    

     

       res.append(None)
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 else:
     
    
   

    

     

    
    

     
 for i in range(st, end + 1):
     
    
   

    

     

    
    

     

       left = dfs(st, i - 1)
     
    
   

    

     

    
    

     

       right = dfs(i + 1, end)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 for l in left:
     
    
   

    

     

    
    

     
 for r in right:
     
    
   

    

     

    
    

     

       node = TreeNode(i)
     
    
   

    

     

    
    

     

       node.left = l
     
    
   

    

     

    
    

     

       node.right = r
     
    
   

    

     

    
    

     

       res.append(node)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 return dfs(1, n)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       n = 3
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       ans = s.generateTrees(n)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/108715933