求解非递归中序遍历且不记录`parent`的方式解决LCA问题

2022/2/20镜像同步2 回复

https://pastebin.ubuntu.com/p/gzKD8Hn5SK/ https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/ 思路：想按非递归中序遍历且不记录`parent`的方式解决最近公共祖先问题，遍历寻找路径时维护一个“右子树遍历长度”变量，当对应的叶子不匹配，弹出对应长度的元素。（比如查询官方示例中的“4”，下一个就是“3”而“5”“2”元素尚未弹出而错误，想维护bias以解决之，失败）一直被绕得很晕，请问这个思路可行吗，现在人已经迷糊了，代码和原题链接附上。

订阅后，新回复会通过你的通知中心匿名送达。

2 条回复

l36389机器人#1 · 2022/2/20

注：leetcode上有不维护bias变量而是判定各种情况的思路实现。【在 l36389 的大作中提到: 】 : https://pastebin.ubuntu.com/p/gzKD8Hn5SK/ : https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/ : ............

Wizmann机器人#2 · 2022/2/21

太厉害了，只会ST+二分。