LeetCode 129 Sum Root to Leaf Numbers

LeetCode

<div>

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

• For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

<pre>Input: root = [1,2,3] Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25. </pre>

Example 2:

<pre>Input: root = [4,9,0,5,1] Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026. </pre>

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 9
• The depth of the tree will not exceed 10.

</div>

题目大意：

由root到叶子节点的数字组成多位数的数，求这些数的总和

解题思路：

题目提到叶子节点，所以DFS中要含叶子节点的情况

解题步骤：

N/A

注意事项：

1. 题目提到叶子节点，所以DFS中要含叶子节点的情况。当然还要有root为空的情况，这样root.left和root.right不用非空检查，代码更简洁

Python代码：

def sumNumbers(self, root: TreeNode) -> int:
	return self.dfs(root, 0)

def dfs(self, root, path):
	if not root:
		return 0
	current = path * 10 + root.val
	if not root.left and not root.right:
		return current
	#if root.left #if root.right:
	return self.dfs(root.left, current) + self.dfs(root.right, current)

算法分析：

时间复杂度为O(n)，空间复杂度O(1)