本文最后更新于 2025-03-31T00:09:09+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
| 给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字:
例如,从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。
叶节点 是指没有子节点的节点。
示例 1:
输入:root = [1,2,3] 输出:25 解释: 从根到叶子节点路径 1->2 代表数字 12 从根到叶子节点路径 1->3 代表数字 13 因此,数字总和 = 12 + 13 = 25
示例 2:
输入:root = [4,9,0,5,1] 输出:1026 解释: 从根到叶子节点路径 4->9->5 代表数字 495 从根到叶子节点路径 4->9->1 代表数字 491 从根到叶子节点路径 4->0 代表数字 40 因此,数字总和 = 495 + 491 + 40 = 1026
提示:
树中节点的数目在范围 [1, 1000] 内 0 <= Node.val <= 9 树的深度不超过 10
|
题目思路
- 1、DFS 与 BFS 题目,DFS 变式多,BFS 单一,更简单。
代码块。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
class Solution { public: int sumNumbers(TreeNode* root) {
if(root == nullptr) return 0; int sum = 0; queue<TreeNode* >q1; queue<int> q2; q1.push(root); q2.push(root -> val); while(q1.empty() == 0) { TreeNode* n = q1.front(); int num = q2.front(); q1.pop();q2.pop(); TreeNode* l = n -> left; TreeNode* r = n -> right; if(l == nullptr && r == nullptr) sum += num; else { if(l != nullptr) { q1.push(l); q2.push(num * 10 + l -> val); } if(r != nullptr) { q1.push(r); q2.push(num * 10 + r -> val); } } } return sum; } };
|
复杂度
Day-15 129. 求根节点到叶节点数字之和
https://chaggle.github.io/2021/09/24/Leetcode/91-day/day-15/