统计根到叶路径字符串为目标串子序列的路径数
哪些公司问过
答案要点
- 子序列只要求保持相对顺序、不要求连续,贪心匹配最早出现位置即可判定
- DFS 沿路径传递已匹配位置 j,回溯时自动恢复,无需拷贝路径串
- 预处理 next[i][c] 表,使每个节点的匹配推进为 O(1)
- 某节点匹配失败时整棵子树都可剪枝,只在叶子处计数
- 时间 O(n + m·Σ),并处理空树、单节点、多字符节点值等边界
易错点
- 把子序列当成子串,要求连续匹配
- 在非叶子节点就计数,或把只有一个孩子的节点当成叶子
- 每条路径都拼出完整字符串再判定,复杂度明显变高
面试官常见追问
- 请实现二叉树的数据结构定义。
- 如果反过来要求目标串是路径串的子序列怎么办?
- 为什么贪心匹配最早位置是对的?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场