共计 1879 个字符,预计需要花费 5 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 1022. 从根到叶的二进制数之和 ,难度为 简略。
Tag :「DFS」、「BFS」、「二叉树」、「树的遍历」
给出一棵二叉树,其上每个结点的值都是 $0$ 或 $1$。每一条从根到叶的门路都代表一个从最高无效位开始的二进制数。
例如,如果门路为 0 -> 1 -> 1 -> 0 -> 1
,那么它示意二进制数 01101
,也就是 $13$。
对树上的每一片叶子,咱们都要找出从根到该叶子的门路所示意的数字。
返回这些数字之和。题目数据保障答案是一个 $32$ 位 整数。
示例 1:
输出:root = [1,0,1,0,1,0,1]
输入:22
解释:(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22
示例 2:
输出:root = [0]
输入:0
提醒:
- 树中的节点数在 $[1, 1000]$ 范畴内
Node.val
仅为 $0$ 或 $1$
递归
容易想到「递归」进行求解,在 DFS
过程中记录下以后的值为多少,假如遍历到以后节点 $x$ 前,记录的值为 $cur$,那么依据题意,咱们须要先将 $cur$ 进行整体左移(腾出最初一位),而后将节点 $x$ 的值搁置最低位来失去新的值,并持续进行递归。
递归有应用「函数返回值」和「全局变量」两种实现形式。
代码:
class Solution {public int sumRootToLeaf(TreeNode root) {return dfs(root, 0);
}
int dfs(TreeNode root, int cur) {int ans = 0, ncur = (cur << 1) + root.val;
if (root.left != null) ans += dfs(root.left, ncur);
if (root.right != null) ans += dfs(root.right, ncur);
return root.left == null && root.right == null ? ncur : ans;
}
}
–
class Solution {
int ans = 0;
public int sumRootToLeaf(TreeNode root) {dfs(root, 0);
return ans;
}
void dfs(TreeNode root, int cur) {int ncur = (cur << 1) + root.val;
if (root.left != null) dfs(root.left, ncur);
if (root.right != null) dfs(root.right, ncur);
if (root.left == null && root.right == null) ans += ncur;
}
}
- 工夫复杂度:$O(n)$
- 空间复杂度:疏忽递归带来的额定空间开销,复杂度为 $O(1)$
迭代
天然也能够应用「迭代」进行求解。
为了不引入除「队列」以外的其余数据结构,当咱们能够把某个节点 $x$ 放出队列时,先将其的值批改为以后遍历门路对应的二进制数。
代码:
class Solution {public int sumRootToLeaf(TreeNode root) {
int ans = 0;
Deque<TreeNode> d = new ArrayDeque<>();
d.addLast(root);
while (!d.isEmpty()) {TreeNode poll = d.pollFirst();
if (poll.left != null) {poll.left.val = (poll.val << 1) + poll.left.val;
d.addLast(poll.left);
}
if (poll.right != null) {poll.right.val = (poll.val << 1) + poll.right.val;
d.addLast(poll.right);
}
if (poll.left == null && poll.right == null) ans += poll.val;
}
return ans;
}
}
- 工夫复杂度:$O(n)$
- 空间复杂度:$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1022
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
本文由 mdnice 多平台公布