leetcode 129. Sum Root to Leaf Numbers (求根到叶子节点数字之和)

题目要求

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。
例如，从根到叶子节点路径 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。

说明: 叶子节点是指没有子节点的节点。

解题思路

主要的思想是，我们对每一层的节点进行拼接和累加，什么意思呢？看example1,我们需要拼接1，2和1，3两个数字为12，13。之后因为他们是叶子节点，所以我们要把他们加起来。 如何拼接呢？ 最简单的方法，我们使用字符串的形式。这样直接进行数字的拼接就可以了，不用再去个位，十位的进行转换。非常好理解。
要点：
（1）字符串拼接数字
（2）到叶子节点进行累加和。

主要代码python

# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution(object):def sumNumbers(self, root):""":type root: TreeNode:rtype: int"""if root is None:return 0self.result = 0self.dfs(root, '')return self.result# 递归搜索过程，遇到叶子结点就进行累加操作def dfs(self, node, s):if not node.left and not node.right:self.result += int(s + str(node.val))if node.left:self.dfs(node.left, s+str(node.val)) # s + str(node.val) 是到现在目前为止的数 如ex2中的节点9 就是‘49’if node.right:self.dfs(node.right, s+str(node.val))  

原题链接：https://leetcode.com/problems/sum-root-to-leaf-numbers/