从根到叶的二进制数之和

题目描述：

给出一棵二叉树，其上每个结点的值都是 0 或 1 。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13 。
对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位 整数。

示例 1：

输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
示例 2：

输入：root = [0]
输出：0

提示：

树中的节点数在 [1, 1000] 范围内
Node.val 仅为 0 或 1

思路:

时间复杂度：O(n),空间复杂度O(1)

只要递归求出二叉树叶子节点的值就行

代码:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
    sum,res := 0,0
    var dfs func(root *TreeNode)
    dfs = func(root *TreeNode){
        sum = sum*2+root.Val
        if root.Left != nil{
            dfs(root.Left)
        }
        if root.Right != nil{
            dfs(root.Right)
        }
        if root.Left == nil && root.Right == nil{
          
            res += sum
        }
        sum /=2
        
    }
    dfs(root)
    return res
}

代码效率：

执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.9 MB, 在所有 Go 提交中击败了80.30%的用户