leetcode 894 . 所有可能的满二叉树

题解

递归,满二叉树对应的N一定不会是偶数,每一个节点的左边或右边可能有1、3、5、7…等奇数个节点

示例代码(go)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func allPossibleFBT(N int) []*TreeNode {
arr := make([]*TreeNode, 0)
if N % 2 == 0 {
return arr
}
if N == 1 {
arr = append(arr, new(TreeNode))
return arr
}
for i := 1; i < N; i+=2 {
left := allPossibleFBT(i)
right := allPossibleFBT(N-i-1)
for _, lt := range left {
for _, rt := range right {
node := new(TreeNode)
node.Left = lt
node.Right = rt
arr = append(arr, node)
}
}
}
return arr
}