牛客571235959号

题解

/ 注册

全部文章 / 题解（共1篇）

题解 |符合空间复杂度O(1)的二叉树最近公共祖先解法（Morris遍历）

题目要求空间复杂度为O(1)，使用递归和堆缓存的方式遍历均不符合要求，考虑使用Morris遍历(Morris遍历过程不在赘述)。同样，使用记录公共路径方法均会超过空间复杂度要求，下面简述种算法，供参考。【场景分析】前序遍历，找到第一个目标节点 T1；第二个目标节点 T2有两种情况：1）在T...

C++ 二叉树

2021-12-09

1 1140