树能收集

2025年Java面试宝典网盘下载链接（提取码：9b3g）建议保存在自己的网盘里随时查阅，整理了三年的互联网大厂真实面试题，覆盖所有高频考点。

从二叉树到多叉树：树结构面试解题全攻略

做算法题时，我们常常需要收集树结构的数据——无论是前序遍历时存储节点路径，还是层序遍历时记录每层节点值。这种收集过程就像用渔网捞鱼，网眼大小（收集规则）和撒网方式（遍历方法）直接影响结果。

一、为什么要重视树结构的收集操作？

在真实面试场景中，每道树相关题目都包含显性或隐性的数据收集需求。例如：

1. 层序遍历要求按层级收集节点值，形成二维数组
2. 路径总和需要收集从根节点到叶子节点的所有路径
3. 最近公共祖先问题本质是收集两个目标节点的路径特征

在实际编码中，很多同学会遇到这些问题：

• 递归时临时变量被错误覆盖
• 非递归写法中容器使用不当
• 多层嵌套导致时间复杂度失控

二、掌握三种核心收集模式

2.1 递归式收集（深度优先）

这种模式最适合路径类问题。需要特别注意递归的传参方式：

void dfs(TreeNode node, List<Integer> path) {
    // 递阶段收集
    path.add(node.val);
    // 处理子节点
    dfs(node.left, path);
    dfs(node.right, path);
    // 归阶段清理
    path.remove(path.size()-1);
}

通过这种"栈式管理"可以精准控制每个路径分支的数据收集范围。记得在找到目标路径时进行深拷贝（new ArrayList<>(path)），避免后续修改污染结果。

2.2 迭代式收集（广度优先）

层序遍历的经典模板：

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> level = new ArrayList<>();
    for(int i=0; i<size; i++){
        TreeNode cur = queue.poll();
        level.add(cur.val); // 收集当前层数据
        // 添加子节点...
    }
    result.add(level);
}

注意在while循环内先记录当前队列长度，这个技巧能精确控制每层节点的收集范围。当遇到N叉树的层序遍历时，只需把添加子节点的逻辑改为遍历children列表即可。

2.3 特征收集（哈希表/前缀和）

这类高阶用法常见于复杂问题，例如：

• 二叉树中指定路径和的数量
• 子树特征匹配
• 路径编码

可以配合哈希表存储中间状态：

Map<Integer, Integer> prefixSum = new HashMap<>();
prefixSum.put(0, 1); // 初始化空路径
int currentSum = 0;

通过维护路径和的累积值，可以快速判断是否存在满足条件的路径。这种数据收集方式将时间复杂度从O(N²)优化到O(N)。

三、避开四大常见陷阱

1. 路径污染：递归回溯时忘记删除已处理节点
2. 引用传递：直接添加可变对象（如List）而未做拷贝
3. 层级混淆：层序遍历时错误判断当前层级
4. 空间爆炸：过度收集不必要的数据导致内存占用过高

推荐大家在面试鸭返利网获取更多实战技巧，如果需要购买面试鸭会员，通过该网站下单可返利25元，相当于用更优惠的价格获得全站题库资源。

四、工程化实践建议

在实际编码时要注意：

1. 对于大规模树结构，优先选择迭代法避免栈溢出
2. 收集字符串路径时使用StringBuilder提升性能
3. 多叉树的处理要注意children判空
4. 合理使用自定义对象封装多个参数

把每次树的数据收集看作一个微型系统设计，想清楚：

• 收集的触发时机（何时开始/结束）
• 存储介质的选择（List/Map/Set）
• 数据生命周期管理（何时创建/修改/销毁）

通过系统化的思维训练，你会逐渐形成自己的解题模板库。当面试官要求实现一个树的锯齿形层序遍历时，你会立刻反应过来：这不过是基础层序遍历加上奇偶层判断的数据收集策略而已。