一、简介

题目：95. 不同的二叉搜索树 II

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

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

二、实现

思路：二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。假设arr为[1~n]组成的数组，如果某个节点为arr[i]，那么该节点左子树是由arr[0]~arr[i-1]之间值组成的不同二叉搜索树; 那么该节点右子树是由arr[i]~arr[n]直接的值组成的不同的二叉搜索树。如下：

arr[i] 左子树为 {arr[0]~arr[i-1]}组成的任意一个的二叉搜索树

arr[i] 右子树为 {arr[i+1]~arr[n]}组成的任意一个的二叉搜索树

/**
 * 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 doGenerateTrees(1, n)
}


func doGenerateTrees(start, end int) []*TreeNode {
    if start > end {
        return nil
    }

    treeList := make([]*TreeNode, 0)
    if start == end {
        curNode := &TreeNode{
            Val:   start,
            Left:  nil,
            Right: nil,
        }

        treeList = append(treeList, curNode)
        return treeList
    }

    for i := start; i <= end; i++ { // start-> i 左节点, i-> end 为 右节点， i为跟节点
        var (
            leftList  []*TreeNode
            rightList []*TreeNode
        )

        if start <= i-1 {
            leftList = doGenerateTrees(start, i-1)
        }
        if end >= i+1 {
            rightList = doGenerateTrees(i+1, end)
        }

        if len(leftList) != 0 && len(rightList) != 0 {
            for _, leftNode := range leftList {
                for _, rightNode := range rightList {
                    curNode := &TreeNode{
                        Val:   i,
                        Left:  leftNode,
                        Right: rightNode,
                    }

                    treeList = append(treeList, curNode)
                }
            }
        } else if len(rightList) != 0 {
            for _, rightNode := range rightList {
                curNode := &TreeNode{
                    Val:   i,
                    Left:  nil,
                    Right: rightNode,
                }

                treeList = append(treeList, curNode)
            }
        } else if len(leftList) != 0 {
            for _, leftNode := range leftList {
                curNode := &TreeNode{
                    Val:   i,
                    Left:  leftNode,
                    Right: nil,
                }

                treeList = append(treeList, curNode)
            }
        }
    }

    return treeList
}