抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

19 | 面试题:二叉树&二叉搜索树的最近公共祖先

236. 二叉树的最近公共祖先

解法一:Path,寻找路径,看路径最早重合的地方。从根节点往下找,找到需要查找的两个节点的路径,然后判断最早重合点。

时间复杂度:查找第一个节点O(N) + 查找第二个节点O(N) +从根节点开始的最早重合点 ≈ 3O(N) ,忽略常数,最终:O(N)

相对较慢,同时代码复杂,但思维逻辑直接。

特例:从每个节点往上找,就变成了寻找两个链表的重合点,但一般不会有往上的指针,所以是特例。

拓展:因为是树,重合的地方比较好判断,如果不是树呢?这里就有了一个新问题,链表重合:剑指 Offer 52. 两个链表的第一个公共节点

解法二:递归(Recursion),使用一个辅助函数 findPorQ(root, P, Q),从以 root 为根的子树上去找 P 和 Q,返回任意一个均可。

伪代码:

fun findPorQ(root, P, Q){
   if(root == P or root ==Q) return root
   findPorQ(root.left, P, Q)
   findPorQ(root.right, P, Q)
}

原理:层层递归,如果两边都能找到 P 或者 Q,说明当前节点就是公共节点。

如果一侧找不到为空,则可以放弃为空的那一侧,继续递归另一侧。

Java 代码很好理解(注意嵌套的三目运算符):

变种题:235. 二叉搜索树的最近公共祖先

解法:根据二叉搜索树的规律,判断 P 和 Q 与 root 节点的相对关系即可。P,Q 都小于 root 则在左子树中,都大于则在右子树中,刚刚一大一小则当前就是。

Python 版本:递归

非递归:


0条评论

发表评论