Leetcode--Java--95. 不同的二叉搜索树 II

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

DFS 爆搜

核心思路 将l，r看成二叉搜索树中序遍历的左右边界。

1. 枚举根结点的位置，然后枚举左边左子树的数量，再枚举右边右子树的数量，最后由乘法原理，相乘总数量就是所有二叉树的数量。

class Solution {
    public List generateTrees(int n) {
     if (n == 0) return new ArrayList();
     //枚举根结点的位置，l,r看成BST的左右边界
    return dfs(1, n);
    }

    public List dfs(int l, int r) {
        List res = new ArrayList<>();
        if (l > r) {
            res.add(null);
            return res;
        }
        //循环枚举
    for (int i = l; i <= r; i ++ ) {
        //拿到左右子树
        List leftTree = dfs(l, i - 1), rightTree = dfs(i + 1, r);
        //枚举左右子树拼接到根结点，创建二叉BST
        for (TreeNode ltree: leftTree) {
            for (TreeNode rtree: rightTree) {
                //创建根结点
                TreeNode root = new TreeNode(i);
                root.left = ltree;
                root.right = rtree;
                res.add(root);
            }
        }
    }
    return res;
  }
}