算法-BST-不同的二叉搜索树 II

你的名字 2023-02-28 11:24 14阅读 0赞

# 算法-BST-不同的二叉搜索树 II #

# 1 题目概述 #

## 1.1 题目出处 ##

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

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2 递归 #

## 2.1 思想 ##

每次遍历 start->end，依次取来作为root，然后分别找两边的所有可能子树组成的子树list，并将左子树list和右子树list双重遍历组合所有可能来分别作为root的left和right，放入resultList。

## 2.2 代码 ##

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
    class Solution { 
        public List<TreeNode> generateTrees(int n) { 
            if(n == 0){ 
                return new ArrayList<>();
            }
    
            return gen(1, n);
        }
        private List<TreeNode> gen(int start, int end){ 
            List<TreeNode> resultList = new ArrayList<>();
            if(start > end){ 
                // 直接返回null不便于遍历
                // return null;
                resultList.add(null);
                return resultList;
            }
            if(start == end){ 
                resultList.add(new TreeNode(start));
                return resultList;
            }
    
            for(int i = start; i <= end; i++){ 
                List<TreeNode> lefts = gen(start, i - 1);
                List<TreeNode> rights = gen(i + 1, end);
                for(TreeNode left : lefts){ 
                    for(TreeNode right : rights){ 
                        TreeNode root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        resultList.add(root);
                    }
                }
            }
            return resultList;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200721115359419.png]  
![在这里插入图片描述][20200721115422183.png]

# 参考文档 #

*  [LeetCode官方题解][LeetCode]
 *  [详细通俗的思路分析，多解法][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20230209/9cb281a67090405abbdbffa940fff435.png
[20200721115359419.png]: https://img-blog.csdnimg.cn/20200721115359419.png
[20200721115422183.png]: https://img-blog.csdnimg.cn/20200721115422183.png
[LeetCode]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/
[Link 1]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-2-7/