129. Sum Root to Leaf Numbers

Information

  • Diffculty: Medium

  • Created: 2020-01-12 17:34:39

  • Last Motified: 2020-01-12 17:34:39

  • Tags: Tree, Depth-first Search

Intuition

The key point of this problem if to get the number of each leaves. To get it, we could add an additional variable to the DFS method to pass the previous number from the root to its parent.

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self._numbersum = 0
        self._helper(root, 0)
        return self._numbersum

    def _helper(self, node, previous):
        if node is None:
            return
        value = previous * 10 + node.val
        if node.left == node.right == None:
            self._numbersum += value
        self._helper(node.left, value)
        self._helper(node.right, value)