leetcode 95. Unique Binary Search Trees II | 96. Unique Binary Search Trees

布满荆棘的人生 2022-09-10 03:13 170阅读 0赞

## 95. Unique Binary Search Trees II ##

[https://leetcode.com/problems/unique-binary-search-trees-ii/][https_leetcode.com_problems_unique-binary-search-trees-ii]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

题是好题，可惜我自己想不出来，后来偷看了答案。

难点在于在何处进行 list.add(root);，以及在修改树的形状时候，如何实现所谓的“深拷贝”，而不让树与树之间相互影响。

/** * 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) { 
            return genRange(1, n);
        }
    
        public List<TreeNode> genRange(int begin, int end) { 
            List<TreeNode> list = new ArrayList<>();
            if (begin > end) { 
                list.add(null);
                return list;
            }
            for (int i = begin; i <= end; i++) { 
                List<TreeNode> leftRoots = genRange(begin, i - 1);
                List<TreeNode> rightRoots = genRange(i + 1, end);
                for (TreeNode left : leftRoots) { 
                    for (TreeNode right : rightRoots) { 
                        TreeNode root = new TreeNode(i);
                        root.left = left;
                        root.right = right;
                        list.add(root);
                    }
                }
            }
            return list;
        }
    }

## 96. Unique Binary Search Trees ##

[https://leetcode.com/problems/unique-binary-search-trees/][https_leetcode.com_problems_unique-binary-search-trees]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 题解 ##

本题虽然是 I，但比上题要多一个 dp，因为 n 的范围比较大，而且只要返回最后的组合个数就行了，所以 dp map 中记录 range 中的数字个数即可，不需要记录 begin 和 end。

class Solution { 
        Map<Integer, Integer> map;
    
        public int numTrees(int n) { 
            map = new HashMap<>();
            return numRange(1, n);
        }
    
    
        public int numRange(int begin, int end) { 
            if (begin > end) return 1;
            if (map.containsKey(end - begin + 1)) return map.get(end - begin + 1);
            
            int sum = 0;
            for (int i = begin; i <= end; i++) { 
                int leftSum = numRange(begin, i - 1);
                int rightSum = numRange(i + 1, end);
                sum += (leftSum * rightSum);
            }
            map.put(end - begin + 1, sum);
            return sum;
        }
    }

[https_leetcode.com_problems_unique-binary-search-trees-ii]: https://leetcode.com/problems/unique-binary-search-trees-ii/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/d37ab7a99b3d4f2a82cffb05d25b0a8a.png
[https_leetcode.com_problems_unique-binary-search-trees]: https://leetcode.com/problems/unique-binary-search-trees/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/0d2cace378f94e1a881a4674bf16faad.png