查找树中路径和大于阈值的路径
哪些公司问过
答案要点
- 先确认路径定义:根到叶、根到任意节点,还是任意向下路径
- DFS 维护路径数组和当前和,到叶子时判断是否大于阈值
- 回溯时弹出当前节点,保证路径状态正确
- 满足条件时拷贝路径,最坏 O(n·h),递归空间 O(h)
- 节点值非负时超过阈值的子树可整体收集;注意负数与溢出
易错点
- 回溯时没有弹出当前节点,路径串到其他分支
- 把路径数组的引用直接放进结果,后续修改导致结果被改掉
- 在非叶子节点就收集,与根到叶的要求不符
面试官常见追问
- 路径可以从任意节点开始向下怎么办?
- 如何用迭代实现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场