LeetCode 129, 133, 136
129. 求根节点到叶节点数字之和
题目链接
标签
树 深度优先搜索 二叉树
思路
由于本题需要 从 根节点 遍历到 叶子节点（无子节点的节点叫做叶子节点），所以可以使用 深度优先搜索 的思想：每次遍历一个节点就计算 当前的路径（从根节点到当前节点）所表示的数字，然后将其传递给它的两棵子树，对 在两棵子树求得的所有路径之和 求和 并 返回。
像这样从 根节点 向 叶子节点 遍历，如果遍历到叶子节点，则返回 从 根节点 到 此叶子节点 的路径所表示的数字。此外，可能会遇到一个当前节点为 null 的情况，此时返回 0 作为路径即可。
代码
class Solution {
public int sumNumbers(TreeNode root) {
return dfs(root, 0);
}
// curr 是当前遍历的节点，currNum 是从根节点到 curr 的路径所表示的数字
private int dfs(TreeNode curr, int currNum) {
if (curr == null) { // 如果 curr 为 null
return 0; // 则返回 0
}
int num = currNum * 10 + curr.val; // 计算从根节点到 curr 的路径所表示的数字
if (curr.left == null && curr.right == null) { // 如果到叶子节点
return num; // 则返回从根节点到这个叶子节点的路径所表示的数字
}
return dfs(curr.left, num) // 遍历左子树，求左子树中的所有路径之和
+ dfs(curr.right, num); // 遍历右子树，求右子树的所有路径之和
}
}
133. 克隆图
题目链接
标签
深度优先搜索 广度优先搜索 图 哈希表
思路
本题和 LeetCode 138. 随机链表的复制 类似，使用的方法完全一样，都是 建立旧节点与新节点的映射，不过与之不同的一点是：138 题中链表的结构没有这么复杂，而本题将基础链表中的 next 指针变成了一个 neighbors 指针集合，这就意味着本题无法像 138 题一样遍历链表来为新节点的属性赋值，而需要使用别的遍历方式——深度优先搜索（本方式复用了 cloneGraph() 方法，求旧节点所对应的新节点）：
- 如果旧节点为
null，则返回null。 - 如果已经建立过 旧节点 和 新节点 的映射，则直接返回新节点。
- 如果没有建立 旧节点 和 新节点 的映射，则需要构建新节点，分为以下三步：
- 创建新节点：给新节点的
val属性赋值。 - 保存 旧节点 和 新节点 的映射。
- 给新节点的
neighbors属性赋值：构建新节点之间的neighbor关系。
- 创建新节点：给新节点的
注意：构建新节点的第二、三步不能调换顺序。因为本节点的 neighbor 的 neighbor 是本节点，这两个节点之间会 互相获取对方的新节点，而 要返回本节点的新节点就需要先获取对方节点的新节点，从而进入死循环。
代码
class Solution {
// 给定一个旧节点，返回其对应的新节点
public Node cloneGraph(Node oldNode) {
if (oldNode == null) { // 如果 旧节点 为 null
return null; // 则返回 null
}
if (mapper.containsKey(oldNode)) { // 如果已经建立过 旧节点 和 新节点 的映射
return mapper.get(oldNode); // 则直接返回 旧节点 对应的 新节点
}
// 构建 新节点，给新节点的 neighbors 链表初始化指定的大小，避免 后续扩容 浪费时间
Node newNode = new Node(oldNode.val, new ArrayList<>(oldNode.neighbors.size()));
mapper.put(oldNode, newNode); // 先保存 旧节点 和 新节点 的映射
for (Node neighbor : oldNode.neighbors) { // 然后再构建新节点之间的 neighbor 关系
// 按照顺序寻找 新节点 对应的 新 neighbor
newNode.neighbors.add(cloneGraph(neighbor));
}
return newNode; // 返回新节点
}
// 映射 旧节点 和 新节点 的映射，key 为 旧节点，value 为 新节点
private Map<Node, Node> mapper = new HashMap<>();
}
136. 只出现一次的数字
题目链接
标签
位运算 数组
思路
异或的定义是：相同为假，不同为假。例如对于两个二进制数 0101, 1001，它们异或的结果为 0101 ^ 1001 = 1100。
本题考查了一个位运算的知识：对两个数使用 异或 操作得到的结果如下：
- 如果两个数相等，则结果为
0。这是因为两个数相等代表其二进制数相等，而相同为假，所以异或的结果全是0，从而两个相等的数的异或结果为0。 - 如果是
0 ^ 某个数，则结果为某个数。这种情况举个例子更好理解：例如对于0000, 1101，它们异或的结果为1101，恰好与这个数相等。 - 对于其他情况，结果通常没有具体意义。
多个数进行异或操作 就是 复合了多个 两数异或 的结果，例如 0011 ^ 1100 ^ 0011 = 0 ^ 1100 = 1100。
所以可以遍历数组，对所有数使用异或操作，出现两次的数都抵消成 0 了，出现一次的数最终和 0 进行异或操作，得到它本身。
代码
class Solution {
public int singleNumber(int[] nums) {
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
res ^= nums[i];
}
return res;
}
}
原文地址：https://blog.csdn.net/qq_61350148/article/details/140604559
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！