当前位置： 面试刷题>> 求根节点到叶节点数字之和(经典算法150题)
### 题目描述
给定一个二叉树，树的每个节点都包含一个数字（`0-9`），这棵树的每条从根到叶的路径都代表一个数字。例如，路径`1 -> 2 -> 3`表示数字`123`。
计算从根到叶的所有路径所表示的数字之和。
**示例**：
```
1
/ \
2 3
```
这棵树的根到叶的路径分别为`1->2`和`1->3`，它们分别表示数字`12`和`13`，因此数字之和为`12 + 13 = 25`。
### PHP 示例代码
```php
class TreeNode {
public $val;
public $left;
public $right;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
function sumNumbers($root) {
return dfs($root, 0);
}
function dfs($node, $currentSum) {
if ($node === null) {
return 0;
}
// 更新当前路径的数字和
$currentSum = $currentSum * 10 + $node->val;
// 到达叶子节点，返回当前路径的和
if ($node->left === null && $node->right === null) {
return $currentSum;
}
// 递归左右子树，并累加结果
return dfs($node->left, $currentSum) + dfs($node->right, $currentSum);
}
// 示例用法
$root = new TreeNode(1);
$root->left = new TreeNode(2);
$root->right = new TreeNode(3);
echo sumNumbers($root); // 输出 25
```
### Python 示例代码
```python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sumNumbers(root):
def dfs(node, current_sum):
if not node:
return 0
current_sum = current_sum * 10 + node.val
if not node.left and not node.right:
return current_sum
return dfs(node.left, current_sum) + dfs(node.right, current_sum)
return dfs(root, 0)
# 示例用法
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sumNumbers(root)) # 输出 25
```
### JavaScript 示例代码
```javascript
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
function sumNumbers(root) {
function dfs(node, currentSum) {
if (!node) return 0;
currentSum = currentSum * 10 + node.val;
if (!node.left && !node.right) {
return currentSum;
}
return dfs(node.left, currentSum) + dfs(node.right, currentSum);
}
return dfs(root, 0);
}
// 示例用法
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
console.log(sumNumbers(root)); // 输出 25
```
这些示例展示了如何使用深度优先搜索（DFS）来解决这个问题，通过递归遍历树的每个路径，并在到达叶子节点时累加路径表示的数字。