Java教程

算法:不同二叉搜索树||

本文主要是介绍算法:不同二叉搜索树||,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 给定一个整数 n,生成所有由 1 ... n 为节点所组成的 二叉搜索树 。

示例:

输入:3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

//1~n 之间的节点能组成几组二叉搜索树

func generateTrees(n int) []*TreeNode {
    if n == 0 {
        return nil
    }

    //1~n之间的节点范围
    return helper(1, n)
}

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

    allTrees := []*TreeNode{}

    // 枚举可行根节点
    for i := start; i <= end; i++ {
        // 获得所有可行的左子树集合
        leftTrees := helper(start, i - 1)
        // 获得所有可行的右子树集合
        rightTrees := helper(i + 1, end)

        // 从左子树集合中选出一棵左子树,从右子树集合中选出一棵右子树,拼接到根节点上
        for _, left := range leftTrees {
            for _, right := range rightTrees {
	//初始化节点值为i,左子树和右子树都为nil
                currTree := &TreeNode{i, nil, nil}
                currTree.Left = left
                currTree.Right = right
                allTrees = append(allTrees, currTree)

            }
        }
    }

    return allTrees
}

 

这篇关于算法:不同二叉搜索树||的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!