共计 951 个字符，预计需要花费 3 分钟才能阅读完成。
从根结点到叶子结点的二进制数字之和
提供一个二进制树，每个结点的值是 0 或者 1.
每一条从根结点到叶子结点的门路，代表一个二进制的数字门路
0 -> 1 -> 1 -> 0 -> 1，代表二进制01101，10 进制是 13
思路天然是递归，一条门路的值，是叶子结点的值 + 下层的值 * 2
深度优先遍历，求取深度的时候，顺便把结点的值代入计算
上面是两个计算形式稍有不同的算法
// 遍历的时候，带着走的是这个结点下层的值
func sum(node n: TreeNode?, sum above: Int?) -> Int{
guard let dot = n else {return 0}
let val = above ?? 0
if dot.left == nil, dot.right == nil {// print(dot.val + val)
return dot.val + val
}
else{
// 进入下一层结点的时候，// 上一层的值 + 该结点的值，再 * 2
// 就是下一层结点的上一层的值
let reduce = (val + dot.val) * 2
return sum(node: dot.left, sum: reduce) + sum(node: dot.right, sum: reduce)
}
}
func sumRootToLeaf(_ root: TreeNode?) -> Int {
guard let n = root else {return 0}
return sum(node: n, sum: nil)
}func sumRootTo(leaf root: TreeNode?) -> Int {
guard let n = root else {return 0}
return dfs(leaf: n, value: 0)
}
// 结点的门路之和，天然是右边门路与左边门路之和
// 计算右边门路的后果时，要带入该结点的值
// 遍历的时候，带着走的是这个结点的值
func dfs(leaf root: TreeNode?, value val: Int) -> Int{
guard let n = root else {return 0}
let reduce = val * 2 + n.val
if n.left == nil, n.right == nil{return reduce}
else{return dfs(leaf: n.left, value: reduce) + dfs(leaf: n.right, value: reduce)
}
}github 链接
正文完