树中最接近路径的节点
难度:
标签:
题目描述
代码结果
运行时间: 52 ms, 内存: 17.8 MB
// 题目思路:
// 使用 Java Stream 进行树的遍历和查找最接近的节点。
// 首先,将树的所有节点收集到一个列表中。
// 然后使用 Stream API 找到与路径最近的节点。
// Java Stream 实现
import java.util.*;
import java.util.stream.*;
public class Solution {
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public TreeNode findClosestNode(TreeNode root, int[] path) {
List<TreeNode> nodes = new ArrayList<>();
collectNodes(root, nodes);
// 使用 Stream API 找到最接近的节点
return nodes.stream()
.min(Comparator.comparingInt(node -> Math.abs(node.val - path[0])))
.orElse(null);
}
private void collectNodes(TreeNode node, List<TreeNode> nodes) {
if (node == null) return;
nodes.add(node);
collectNodes(node.left, nodes);
collectNodes(node.right, nodes);
}
}
解释
方法:
该题解使用了重链剖分(Heavy-Light Decomposition, HLD)的思路来解决树中查询最接近路径的节点的问题。具体思路如下:
1. 通过DFS遍历树,计算每个节点的父节点、子树大小、深度、重儿子等信息。
2. 将树划分为若干重链,每个重链由重儿子连接而成。对于每个节点,记录其所在重链的起点、DFS序等信息。
3. 通过LCA (最近公共祖先)和重链剖分,可以快速计算树中任意两点之间的距离。
4. 对于每个查询(u,v,x),首先判断x是否在u和v的最近公共祖先lca的子树中:
- 如果在,则分别计算x到u和v的LCA的距离,取较近的作为答案。
- 如果不在,则直接返回lca作为最接近路径的节点。
时间复杂度:
O(n+qlogn)
空间复杂度:
O(n)
代码细节讲解
🦆
在构建重链剖分时,如何选择每个节点的重儿子,是基于哪些标准或属性?
▷🦆
如何确保DFS遍历和重链剖分的过程中所计算的DFS序和子树大小是准确的?有没有可能存在节点或连接遗漏导致计算错误?
▷🦆
在计算LCA时,为什么选择比较`top[u]`和`top[v]`的深度,而不是直接比较`u`和`v`的深度?
▷🦆
为什么在查询时需要将节点的索引加1?这是否意味着原始的节点编号是从0开始的,而在HLD类中的处理是从1开始?
▷