leetcode-1022-Sum-of-Root-To-Leaf-Binary-Numbers

发表于   |  

描述

Given a binary tree, each node has value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit. For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf.
Return the sum of these numbers.

Example 1:

img

1
2
3
Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Note:

1
2
3
1. The number of nodes in the tree is between `1` and `1000`.
2. node.val is `0` or `1`.
3. The answer will not exceed `2^31 - 1`.

分析

题目大意是二叉树的每个节点上的数值为0和1，从根节点到叶子节点的一条路径会构成一个二进制字符串，求所有路径构成的二进制字符串转成整数的和。

深度优先遍历二叉树即可。

解决方案1(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        if not root:
            return 0
        self.result = 0
        self.dfs(root, root.val)
        return self.result
        
    def dfs(self, root, preSum):
        if not root.left and not root.right:
            self.result = (self.result + preSum)
            return
        if root.left:
            self.dfs(root.left, preSum*2 + root.left.val)
        if root.right:
            self.dfs(root.right, preSum*2 + root.right.val)

解决方案2(Python)

这种方式不需要引入额外的变量。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def sumRootToLeaf(self, root: TreeNode) -> int:
        if not root:
            return 0
        return self.dfs(root, 0)
        
    def dfs(self, root, preSum):
        if not root:
            return 0
        preSum = preSum * 2 + root.val
        if not root.left and not root.right:
            return preSum
        return self.dfs(root.left, preSum) + self.dfs(root.right, preSum)

解决方案3(Golang)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func sumRootToLeaf(root *TreeNode) int {
    return dfs(root, 0)
}

func dfs(root *TreeNode, preSum int) int {
    if root == nil {
        return 0
    }
    preSum = preSum * 2 + root.Val
    if root.Left == nil && root.Right == nil {
        return preSum
    }
    return dfs(root.Left, preSum) + dfs(root.Right, preSum)
}

题目来源