96. 不同的二叉搜索树
链接
作者：Ethan3014
题目.
难度:middle
解答：tree的定义就是递归的，所以关于树的算法也多采用递归。但是这个递归的话存在子问题重复计算的问题，所以用dp更好
package main
import (
"fmt"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func printTree(root *TreeNode) {
toCheck := make([]*TreeNode, 1)
toCheck[0] = root
toCheckNext := make([]*TreeNode, 0)
for {
stop := true
for _, v := range toCheck {
if v == nil {
toCheckNext = append(toCheckNext, nil, nil)
fmt.Print("nil, ")
} else {
fmt.Print(v.Val, ", ")
toCheckNext = append(toCheckNext, v.Left, v.Right)
stop = false
}
}
fmt.Println("done")
if stop {
break
}
toCheck, toCheckNext = toCheckNext, toCheck[0:0]
}
}
func numTrees(n int) int {
//handle 0, 1, 2
if n <= 2 {
return n
}
dp := make([]int, n+1)
dp[0] = 1 //special case
dp[1] = 1
dp[2] = 2
for i := 3; i = 0; left, right = left+1, right-1 {
dp[i] += dp[left] * dp[right]
}
}
return dp[n]
}
func main() {
fmt.Println(numTrees(3))
}
复杂度分析
time
O(n*n)
spaceO(n)
执行结果执行用时 :
0 ms
, 在所有 Go 提交中击败了
100.00%
的用户
内存消耗 :
1.9 MB
, 在所有 Go 提交中击败了
88.99%
的用户
作者：Ethan3014
