力扣刷题TOP101: 31.BM38 在二叉树中找到两个节点的最近公共祖先

目录：

目的

思路

复杂度

记忆秘诀

python代码

目的：

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找o1 和 o2 的最近公共祖先节点。

---

思路

这个任务目和上一题在二叉搜索树中找到两个节点的最近公共祖先有点类似，都是找最近公共祖先。但是区别在于一个有序一个无序。

力扣刷题TOP101: 30.BM37 二叉搜索树的最近公共祖先-CSDN博客 

特点	普通二叉树	二叉搜索树
数据结构特性	无排序特性，任意结构	左小右大，具有排序特性
算法实现	深度优先搜索(DFS)，逐层递归	利用节点值，逐层比较，不需要完整遍历
时间复杂度	O(n)，需要访问所有节点	O(h)，只需沿着路径查找
适用范围	任意二叉树	仅适用于二叉搜索树
效率	较低	较高

---

代码逻辑：

• 如果当前节点为空

  • 说明这里没有要找的两个节点，直接返回 -1 表示没有找到。

• 如果当前节点就是其中一个目标节点

  • 说明当前节点可能是最近公共祖先（或者它是两个节点之一），直接返回当前节点的值。

• 递归查找左右子树

  • 递归地查找左子树，看是否能找到目标节点之一。如果找到了，返回对应的值；如果没找到，返回 -1。
  • 递归地查找右子树，看是否能找到目标节点之一。如果找到了，返回对应的值；如果没找到，返回 -1。

• 根据左右子树的结果判断

  • 如果左子树没找到（返回 -1），说明两个节点都在右子树，直接返回右子树的结果。
  • 如果右子树没找到（返回 -1），说明两个节点都在左子树，直接返回左子树的结果。
  • 如果左右子树都找到了目标节点，说明当前节点是它们的最近公共祖先，直接返回当前节点的值。

---

示例：假设有以下二叉树，目标是找到节点 4 和 5 的最近公共祖先：

        1/ \2   3/ \4   5

递归过程：

• 从根节点 1 开始：

  • 左子树递归：去节点 2 中查找。
  • 右子树递归：去节点 3 中查找。

• 节点 2 的子树：

  • 左子树递归：在节点 4 找到目标节点 4。
  • 右子树递归：在节点 5 找到目标节点 5。
  • 左右子树都找到目标，返回节点 2 作为最近公共祖先。

• 节点 3 的子树：

  • 左右子树递归：都为空，返回 -1。

• 回到根节点 1：

  • 左子树返回节点 2。
  • 右子树返回 -1。
  • 因为只有左子树找到目标，最终结果是节点 2。

---

复杂度

• 时间复杂度：O(n）

  • 这是一个典型的 深度优先搜索（DFS），每个节点在递归过程中最多会被访问一次。

• 空间复杂度：O(h)

  • 最坏情况下（链表形式的树）：O(h), 其中 h 是树的高度。
  • 最佳情况下（完全平衡的树）：O(log⁡h)。

---

记忆秘诀

• 子树为空，返回无结果
• 当前节点是目标节点，返回自己

• 递归查找左右子树：

  • 两边都找到，当前节点是答案；

  • 只找到一边，继续返回那边结果。

---

python代码

class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Noneclass Solution:def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:# 该子树没找到，返回-1if not root:return -1# 该节点是其中某一个节点if root.val == o1 or root.val == o2:return root.val# 左子树寻找公共祖先left = self.lowestCommonAncestor(root.left, o1, o2)# 右子树寻找公共祖先right = self.lowestCommonAncestor(root.right, o1, o2)# 左子树为没找到，则在右子树中if left == -1:return right# 右子树没找到，则在左子树中if right == -1:return left# 否则是当前节点return root.val

---

* 欢迎大家探讨新思路，能够更好的理解和记忆