384 lines
11 KiB
Markdown
Executable File
384 lines
11 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
|
||
# 129. 求根节点到叶节点数字之和
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/sum-root-to-leaf-numbers/)
|
||
|
||
## 思路
|
||
|
||
本题和[113.路径总和II](https://programmercarl.com/0112.路径总和.html#_113-路径总和ii)是类似的思路，做完这道题，可以顺便把[113.路径总和II](https://programmercarl.com/0112.路径总和.html#_113-路径总和ii) 和 [112.路径总和](https://programmercarl.com/0112.路径总和.html#_112-路径总和) 做了。
|
||
|
||
结合112.路径总和 和 113.路径总和II，我在讲了[二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？](https://programmercarl.com/0112.路径总和.html)，如果大家对二叉树递归函数什么时候需要返回值很迷茫，可以看一下。
|
||
|
||
接下来在看本题，就简单多了，本题其实需要使用回溯，但一些同学可能都不知道自己用了回溯，在[二叉树：以为使用了递归，其实还隐藏着回溯](https://programmercarl.com/二叉树中递归带着回溯.html)中，我详细讲解了二叉树的递归中，如何使用了回溯。
|
||
|
||
接下来我们来看题：
|
||
|
||
首先思路很明确，就是要遍历整个树把更节点到叶子节点组成的数字相加。
|
||
|
||
那么先按递归三部曲来分析：
|
||
|
||
### 递归三部曲
|
||
|
||
如果对递归三部曲不了解的话，可以看这里：[二叉树：前中后递归详解](https://programmercarl.com/二叉树的递归遍历.html)
|
||
|
||
* 确定递归函数返回值及其参数
|
||
|
||
这里我们要遍历整个二叉树，且需要要返回值做逻辑处理，所有返回值为void，在[二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？](https://programmercarl.com/0112.路径总和.html)中，详细讲解了返回值问题。
|
||
|
||
参数只需要把根节点传入，此时还需要定义两个全局遍历，一个是result，记录最终结果，一个是vector<int> path。
|
||
|
||
**为什么用vector类型（就是数组）呢？ 因为用vector方便我们做回溯！**
|
||
|
||
所以代码如下：
|
||
|
||
```
|
||
int result;
|
||
vector<int> path;
|
||
void traversal(TreeNode* cur)
|
||
```
|
||
|
||
* 确定终止条件
|
||
|
||
递归什么时候终止呢？
|
||
|
||
当然是遇到叶子节点，此时要收集结果了，通知返回本层递归，因为单条路径的结果使用vector，我们需要一个函数vectorToInt把vector转成int。
|
||
|
||
终止条件代码如下：
|
||
|
||
```
|
||
if (!cur->left && !cur->right) { // 遇到了叶子节点
|
||
result += vectorToInt(path);
|
||
return;
|
||
}
|
||
```
|
||
|
||
这里vectorToInt函数就是把数组转成int，代码如下：
|
||
|
||
```CPP
|
||
int vectorToInt(const vector<int>& vec) {
|
||
int sum = 0;
|
||
for (int i = 0; i < vec.size(); i++) {
|
||
sum = sum * 10 + vec[i];
|
||
}
|
||
return sum;
|
||
}
|
||
```
|
||
|
||
|
||
* 确定递归单层逻辑
|
||
|
||
本题其实采用前中后序都不无所谓， 因为也没有中间几点的处理逻辑。
|
||
|
||
这里主要是当左节点不为空，path收集路径，并递归左孩子，右节点同理。
|
||
|
||
**但别忘了回溯**。
|
||
|
||
如图：
|
||
|
||
|
||
<img src='https://file1.kamacoder.com/i/algo/129.求根到叶子节点数字之和.png' width=600> </img></div>
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
// 中
|
||
if (cur->left) { // 左 （空节点不遍历）
|
||
path.push_back(cur->left->val);
|
||
traversal(cur->left); // 递归
|
||
path.pop_back(); // 回溯
|
||
}
|
||
if (cur->right) { // 右 （空节点不遍历）
|
||
path.push_back(cur->right->val);
|
||
traversal(cur->right); // 递归
|
||
path.pop_back(); // 回溯
|
||
}
|
||
```
|
||
|
||
这里要注意回溯和递归要永远在一起，一个递归，对应一个回溯，是一对一的关系，有的同学写成如下代码：
|
||
|
||
```CPP
|
||
if (cur->left) { // 左 （空节点不遍历）
|
||
path.push_back(cur->left->val);
|
||
traversal(cur->left); // 递归
|
||
}
|
||
if (cur->right) { // 右 （空节点不遍历）
|
||
path.push_back(cur->right->val);
|
||
traversal(cur->right); // 递归
|
||
}
|
||
path.pop_back(); // 回溯
|
||
```
|
||
**把回溯放在花括号外面了，世界上最遥远的距离，是你在花括号里，而我在花括号外！** 这就不对了。
|
||
|
||
整体C++代码
|
||
|
||
关键逻辑分析完了，整体C++代码如下：
|
||
|
||
```CPP
|
||
class Solution {
|
||
private:
|
||
int result;
|
||
vector<int> path;
|
||
// 把vector转化为int
|
||
int vectorToInt(const vector<int>& vec) {
|
||
int sum = 0;
|
||
for (int i = 0; i < vec.size(); i++) {
|
||
sum = sum * 10 + vec[i];
|
||
}
|
||
return sum;
|
||
}
|
||
void traversal(TreeNode* cur) {
|
||
if (!cur->left && !cur->right) { // 遇到了叶子节点
|
||
result += vectorToInt(path);
|
||
return;
|
||
}
|
||
|
||
if (cur->left) { // 左 （空节点不遍历）
|
||
path.push_back(cur->left->val); // 处理节点
|
||
traversal(cur->left); // 递归
|
||
path.pop_back(); // 回溯，撤销
|
||
}
|
||
if (cur->right) { // 右 （空节点不遍历）
|
||
path.push_back(cur->right->val); // 处理节点
|
||
traversal(cur->right); // 递归
|
||
path.pop_back(); // 回溯，撤销
|
||
}
|
||
return ;
|
||
}
|
||
public:
|
||
int sumNumbers(TreeNode* root) {
|
||
path.clear();
|
||
if (root == nullptr) return 0;
|
||
path.push_back(root->val);
|
||
traversal(root);
|
||
return result;
|
||
}
|
||
};
|
||
```
|
||
|
||
## 总结
|
||
|
||
过于简洁的代码，很容易让初学者忽视了本题中回溯的精髓，甚至作者本身都没有想清楚自己用了回溯。
|
||
|
||
**我这里提供的代码把整个回溯过程充分体现出来，希望可以帮助大家看的明明白白！**
|
||
|
||
|
||
## 其他语言版本
|
||
|
||
### Java：
|
||
|
||
```java
|
||
class Solution {
|
||
List<Integer> path = new ArrayList<>();
|
||
int res = 0;
|
||
public int sumNumbers(TreeNode root) {
|
||
// 如果节点为0，那么就返回0
|
||
if (root == null) return 0;
|
||
// 首先将根节点放到集合中
|
||
path.add(root.val);
|
||
// 开始递归
|
||
recur(root);
|
||
return res;
|
||
}
|
||
|
||
public void recur(TreeNode root){
|
||
if (root.left == null && root.right == null) {
|
||
// 当是叶子节点的时候，开始处理
|
||
res += listToInt(path);
|
||
return;
|
||
}
|
||
|
||
if (root.left != null){
|
||
// 注意有回溯
|
||
path.add(root.left.val);
|
||
recur(root.left);
|
||
path.remove(path.size() - 1);
|
||
}
|
||
if (root.right != null){
|
||
// 注意有回溯
|
||
path.add(root.right.val);
|
||
recur(root.right);
|
||
path.remove(path.size() - 1);
|
||
}
|
||
return;
|
||
}
|
||
public int listToInt(List<Integer> path){
|
||
int sum = 0;
|
||
for (Integer num:path){
|
||
// sum * 10 表示进位
|
||
sum = sum * 10 + num;
|
||
}
|
||
return sum;
|
||
}
|
||
}
|
||
```
|
||
|
||
### Python：
|
||
|
||
```python
|
||
class Solution:
|
||
def sumNumbers(self, root: TreeNode) -> int:
|
||
res = 0
|
||
path = []
|
||
def backtrace(root):
|
||
nonlocal res
|
||
if not root: return # 节点空则返回
|
||
path.append(root.val)
|
||
if not root.left and not root.right: # 遇到了叶子节点
|
||
res += get_sum(path)
|
||
if root.left: # 左子树不空
|
||
backtrace(root.left)
|
||
if root.right: # 右子树不空
|
||
backtrace(root.right)
|
||
path.pop()
|
||
|
||
def get_sum(arr):
|
||
s = 0
|
||
for i in range(len(arr)):
|
||
s = s * 10 + arr[i]
|
||
return s
|
||
|
||
backtrace(root)
|
||
return res
|
||
```
|
||
### Go：
|
||
|
||
```go
|
||
func sumNumbers(root *TreeNode) int {
|
||
sum := 0
|
||
dfs(root, root.Val, &sum)
|
||
return sum
|
||
}
|
||
|
||
func dfs(root *TreeNode, tmpSum int, sum *int) {
|
||
if root.Left == nil && root.Right == nil {
|
||
*sum += tmpSum
|
||
} else {
|
||
if root.Left != nil {
|
||
dfs(root.Left, tmpSum*10 + root.Left.Val, sum)
|
||
}
|
||
if root.Right != nil {
|
||
dfs(root.Right, tmpSum*10 + root.Right.Val, sum)
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
|
||
|
||
### JavaScript：
|
||
|
||
```javascript
|
||
var sumNumbers = function(root) {
|
||
const listToInt = path => {
|
||
let sum = 0;
|
||
for(let num of path){
|
||
// sum * 10 表示进位
|
||
sum = sum * 10 + num;
|
||
}
|
||
return sum;
|
||
}
|
||
const recur = root =>{
|
||
if (root.left == null && root.right == null) {
|
||
// 当是叶子节点的时候，开始处理
|
||
res += listToInt(path);
|
||
return;
|
||
}
|
||
|
||
if (root.left != null){
|
||
// 注意有回溯
|
||
path.push(root.left.val);
|
||
recur(root.left);
|
||
path.pop();
|
||
}
|
||
if (root.right != null){
|
||
// 注意有回溯
|
||
path.push(root.right.val);
|
||
recur(root.right);
|
||
path.pop();
|
||
}
|
||
return;
|
||
};
|
||
const path = new Array();
|
||
let res = 0;
|
||
// 如果节点为0，那么就返回0
|
||
if (root == null) return 0;
|
||
// 首先将根节点放到集合中
|
||
path.push(root.val);
|
||
// 开始递归
|
||
recur(root);
|
||
return res;
|
||
};
|
||
```
|
||
|
||
### TypeScript：
|
||
|
||
```typescript
|
||
function sumNumbers(root: TreeNode | null): number {
|
||
if (root === null) return 0;
|
||
// 记录最终结果
|
||
let resTotal: number = 0;
|
||
// 记录路径中遇到的节点值
|
||
const route: number[] = [];
|
||
// 递归初始值
|
||
route.push(root.val);
|
||
recur(root, route);
|
||
return resTotal;
|
||
function recur(node: TreeNode, route: number[]): void {
|
||
if (node.left === null && node.right === null) {
|
||
resTotal += listToSum(route);
|
||
return;
|
||
}
|
||
if (node.left !== null) {
|
||
route.push(node.left.val);
|
||
recur(node.left, route);
|
||
route.pop();
|
||
};
|
||
if (node.right !== null) {
|
||
route.push(node.right.val);
|
||
recur(node.right, route);
|
||
route.pop();
|
||
};
|
||
}
|
||
function listToSum(nums: number[]): number {
|
||
// 数组求和
|
||
return Number(nums.join(''));
|
||
}
|
||
};
|
||
```
|
||
|
||
### C:
|
||
|
||
```c
|
||
//sum记录总和
|
||
int sum;
|
||
void traverse(struct TreeNode *node, int val) {
|
||
//更新val为根节点到当前节点的和
|
||
val = val * 10 + node->val;
|
||
//若当前节点为叶子节点，记录val
|
||
if(!node->left && !node->right) {
|
||
sum+=val;
|
||
return;
|
||
}
|
||
//若有左/右节点，遍历左/右节点
|
||
if(node->left)
|
||
traverse(node->left, val);
|
||
if(node->right)
|
||
traverse(node->right, val);
|
||
}
|
||
|
||
int sumNumbers(struct TreeNode* root){
|
||
sum = 0;
|
||
|
||
traverse(root, 0);
|
||
|
||
return sum;
|
||
}
|
||
```
|
||
|
||
|