95. 不同的二叉搜索树 II

我会带着你远行 2022-12-24 00:38 130阅读 0赞

# 题目来源 #

[95. 不同的二叉搜索树 II][95. _ II]

# 题目描述 #

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

# 题目解析 #

/**
     * 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 LinkedList<>();
             }
            return helper(1, n);
        }
        
        
        private List<TreeNode> helper(int start, int end){
        
            List<TreeNode> list = new LinkedList<>();
            if (start > end){
        
                list.add(null); // 必须，否则无法进入TreeNode l : left等循环
                return list;
            }
            
            for (int i = start; i <= end; i++){
        
                List<TreeNode> left = helper(start, i - 1);
                List<TreeNode> right = helper(i + 1, end);
                for (TreeNode l : left){
        
                    for (TreeNode r: right){
        
                        TreeNode root = new TreeNode(i);
                        root.left = l;
                        root.right = r;
                        list.add(root);
                    }
                }
            }
            return list;
        }
    
    
    
    }

![在这里插入图片描述][20201125201433321.png_pic_center]

[95. _ II]: https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/b5a2eff1bbf44a25929088bc8d174e66.png
[20201125201433321.png_pic_center]: https://img-blog.csdnimg.cn/20201125201433321.png#pic_center