swift 算法 【二叉树】所有可能的满二叉树

0x00 题目

满二叉树是一类二叉树 其中每个节点恰好有 0 或 2 个子节点 返回包含 N 个节点的所有可能满二叉树的列表 答案的每个元素都是一个可能树的根节点 答案中每个树的每个节点都必须有 node.val = 0 你可以按任何顺序返回树的最终列表

0x01 思路

每个节点恰好有 0 或 2 个子节点 那么加上当前节点 总共是 1 或 3 个节点 所以子节点也只能是 1 个 或 3 个 进而推断出，只有奇数个时 才能构成满二叉树

由于每个元素都是一个可能树的根节点 以 i 为根节点，则 0 到 i-1 构成左子树 i+1 到 N-1 构成右子树 左右子树也是满二叉树 于是原问题变成了更小规模的问题 使用递归来解决

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {

public var val: Int

public var left: TreeNode?

public var right: TreeNode?

public init() { self.val = 0; self.left = nil; self.right = nil; }

public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }

public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {

self.val = val

self.left = left

self.right = right

}

}

解法：

func allPossibleFBT(_ n: Int) -> [TreeNode?] {

// 构建过程中，递归存在重复计算，缓存结果

var cache: [Int:[TreeNode?]] = [:]

func build(_ n: Int) -> [TreeNode?] {

if n == 0 { return [] }

if n == 1 { return [TreeNode(0)] }

var res: [TreeNode?] = []

var i = 1

while i < n - 1 {

// 左子树集合

var leftTrees = cache[i]

if leftTrees == nil {

leftTrees = build(i)

}

// 右子树集合

var rightTrees = cache[n-i-1]

if rightTrees == nil {

rightTrees = build(n-i-1)

}

// 分别从左子树集合中，右子树集合中，拿出一棵子树，组成一棵完整的树

for left in 0..

for right in 0..

let node = TreeNode(0)

node.left = leftTrees![left]

node.right = rightTrees![right]

res.append(node)

}

}

// 偶数个时，无法构建满二叉树，所以遍历奇数

i += 2

}

cache[n] = res

return res

}

let res = build(n)

return res

}

0x03 我的作品

欢迎体验我的作品之一：小五笔 86 版 五笔 从未如此有趣! App Store 搜索即可~

文章来源

 您阅读本篇文章共花了：