【LeetCode with Python】 129. Sum Root to Leaf Numbers

题目

原题页面：https://leetcode.com/problems/sum-root-to-leaf-numbers/
本文地址：</sum-root-to-leaf-numbers/>
题目类型：Tree, Depth-first Search
难度评价：Medium
类似题目：(E) Path Sum, (H) Binary Tree Maximum Path Sum

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

  1
 / \
2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

---

分析

从根节点到叶子节点的路径代表一个数值，找出所有的这些数值然后累加得到一个和。
搜索算法可以用来找可行解，或者找出全部解。找可行解的时候可以用深度优先遍历DFS，或者广度优先遍历BFS。而这个题目则是找出全部解，然后累加全部解。而搜索算法找全部解时的递归解法一般也是两种：自底向上和自顶向下（自己命名的，哈哈）。
就拿这道题来说，自底向上，也就是当递归到叶子节点后，在递归退栈的过程中，让左子树递归返回的数加上右子树递归返回的数。
注意解法中其实用到了乘法分配律，否则每次“归”的时候，就得向上层返回一个数的列表，且越接近root的时候列表会越长。或者记录一个对象内的成员变量，当遍历到叶子节点时，每个叶子节点将到达自身所形成的路径的值加上到成员变量上。

---

代码

class Solution:
    def doSumNumbers(self, root, val):
        if None == root.left and None == root.right:
            return val * 10 + root.val
        left = 0
        right = 0
        if None != root.left:
            left = self.doSumNumbers(root.left, val * 10 + root.val)
        if None != root.right:
            right = self.doSumNumbers(root.right, val * 10 + root.val)
        return left + right

    # @param root, a tree node
    # @return an integer
    def sumNumbers(self, root):
        if None == root:
            return 0
        return self.doSumNumbers(root, 0)