95. 不同的二叉搜索树 II

题意：

解题思路：

思路：
1. 我们从序列1..n中取出数字i，作为树的根节点。于是，剩余 i - 1 个元素可用于左子树，n - i 个元素用于右子树。
        我们只需要把 1 作为根节点，[ ] 空作为左子树，[ 2 ... n ] 的所有可能作为右子树。
      2 作为根节点，[ 1 ] 作为左子树，[ 3...n ] 的所有可能作为右子树。
      3 作为根节点，[ 1 2 ] 的所有可能作为左子树，[] 作为右子树，然后左子树和右子树两两组合。
        n 作为根节点，[ 1... n ] 的所有可能作为左子树，[ ] 作为右子树。
2. 分别递归求出左右子树的所有方案；
3. 左子树的方案加上右子树的方案拼接在一起，构成当前节点的一种方案；
4. 将左右子树的所有方案两两组合，最后记录在res中

PHP代码实现：

class Solution {
    /**
     * @param Integer $n
     * @return TreeNode[]
     */
    function generateTrees($n) {
        if ($n == 0) return [];
        return $this->gen(1, $n);
    }
    function gen($start, $end) {
        $res = [];
        if ($start > $end) {
            array_push($res, null);
        }
        for ($i = $start; $i <= $end; $i++) {
            //左树全排列
            $left = $this->gen($start, $i - 1);
            //右树全排列
            $right = $this->gen($i + 1, $end);
            //所以全排列可能性
            foreach ($left as $l) {
                foreach ($right as $r) {
                    $node = new TreeNode($i);
                    $node->left = $l;
                    $node->right = $r;
                    array_push($res, $node);
                }
            }
        }
        return $res;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return nil
    }
    return dfs(1, n)
}
func dfs(start, end int) []*TreeNode {
    var res []*TreeNode
    if start > end {
        res = append(res, nil)
        return res
    }
    for i := start; i <= end; i++ {
        for _, l := range dfs(start, i-1) {
            for _, r := range dfs(i+1, end) {
                cur := &TreeNode{
                    Val: i,
                }
                cur.Left = l
                cur.Right = r
                res = append(res, cur)
            }
        }
    }
    return res
}