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:

example

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

Note:

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

解法

把问题分解成两个子问题：

1. 找到所有从根节点到叶子节点的路径。

2. 把一条路径上的节点从二进制转为十进制。

两步分开的时间复杂度是 $O(N^2)$。

思路：

1. if root == null，树为空，return 0

2. if root != null，把从 parent 传来的 val 加倍，再加上当前节点的 val

3. if root.left == root.right == None，递归的终点，即叶子节点，返回 val

class Solution:
    def sumRootToLeaf(self, root: TreeNode, val=0) -> int:
        if not root: return 0
        val = val * 2 + root.val
        if root.left == root.right: return val # exit
        return self.sumRootToLeaf(root.left, val) +\
               self.sumRootToLeaf(root.right, val)

参考