深度优先搜索 DFS
解题思路
首先把当前节点的左右子树的值更新，然后递归左右子树，然后左右子树的和即可；
每次把当前位置路径的和 赋值给当前节点，比如 1–>2 就把节点值为2的这个节点值修改为 12 ，所以如果当前节点为叶子节点，直接返回当前节点的值；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树的节点个数，对每个节点访问一次； -
空间复杂度：
O(n)，其中 n 是二叉树的节点个数，空间复杂度主要取决于递归调用的栈空间，递归栈的深度等于二叉树的高度，最坏情况下，二叉树的高度等于节点个数，空间复杂度为O(n)；
代码实现
var sumNumbers = function (root) {
// 1. 根节点为空
if (!root) return 0;
// 2. 叶子节点
if (root.left === null && root.right === null) return root.val;
// 3. 左节点不为空，更新左节点的值
if (root.left) root.left.val = root.val * 10 + root.left.val;
// 4. 右节点不为空，更新右节点的值
if (root.right) root.right.val = root.val * 10 + root.right.val;
// 5. 两个节点都有
return sumNumbers(root.left) + sumNumbers(root.right);
};
广度优先搜索 BFS
解题思路
使用广度优先搜索（层序遍历），需要维护两个队列，分别存储节点和节点对应的数字；
初始时，将根节点和根节点的值分别加入两个队列，每次从两个队列分别取出一个节点和一个数字，进行如下操作：
- 如果当前节点是叶子节点，则将该节点对应的数字加到数字之和；
- 如果当前节点不是叶子节点，则获得当前节点的非空子节点，并根据当前节点对应的数字和子节点的值计算子节点对应的数字，然后将子节点和子节点对应数字分别加入两个队列；
搜索结束后，即可得到所有叶子节点对应的数字之和；
复杂度
-
时间复杂度：
O(n)，其中 n 是二叉树的节点个数，每个节点访问一次； -
空间复杂度：
O(n)，其中 n 是二叉树的节点个数，空间复杂度主要取决于队列，每个队列中的元素个数不会超过 n；
代码实现
var sumNumbers = function (root) {
let sum = 0;
if (root === null) return sum;
const nodeQueue = [];
const numQueue = [];
nodeQueue.push(root);
numQueue.push(root.val);
while (nodeQueue.length) {
const node = nodeQueue.shift();
const num = numQueue.shift();
const left = node.left, right = node.right;
if (left === null && right === null) {
sum += num;
} else {
if (left) {
nodeQueue.push(left);
numQueue.push(num * 10 + left.val);
}
if (right) {
nodeQueue.push(right);
numQueue.push(num * 10 + right.val);
}
}
}
return sum;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 572.另一棵树的子树
上一篇
评论
