二叉树中的最长交错路径(LC1372)
哪些公司问过
答案要点
- 每个节点维护两个状态:第一步向左和第一步向右的最长交错长度
- 转移:L = 左孩子的 R + 1,R = 右孩子的 L + 1,空节点返回 -1
- 路径可从任意节点开始,需要在每个节点更新全局最大值
- 答案按边数计,时间 O(n)、空间 O(h)
易错点
- 只从根节点出发计算,漏掉从中间节点开始的路径
- 把节点数当成边数,结果多 1
- 同方向继续走时把长度清零或继续累加,而不是重置为 1
面试官常见追问
- 自顶向下的写法怎么写?
- 递归太深怎么办?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 二叉树的遍历142 场
- 平衡树的种类与区别:红黑树、AVL、B/B+ 树97 场
- 红黑树的原理与特点67 场
- 二叉树的最近公共祖先 LCA22 场
- 二叉树的最大深度17 场
- 二叉树的最大路径和15 场
- 对称二叉树(判断镜像)13 场
- 二叉树的 Z 字形层序遍历13 场
- 二叉树的直径8 场
- 二叉搜索树转双向链表7 场