跟随carl代码随想录刷题
语言：python

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

题目：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
.
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
👉示例1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
👉示例2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
👉示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

题目分析

思路：自底向上——回溯（后序遍历）
后序遍历就是一个天然的回溯过程，最先处理的一定是叶子节点。

🙋如何判断一个节点是节点p和节点q的公共祖先呢？
💁如果找到一个节点，发现：

• 左子树出现节点p，右子树出现节点q，
• 或 左子树出现节点q，右子树出现节点p
• 或 节点p本身拥有一个子孙节点q
• 或 节点q本身拥有一个子孙节点p

那么该节点就是节点p和节点q的最近公共祖先。

递归思想：找到祖先后，返回return root。经过递归层层返回，如果有值，就是祖先，如果为None，就是没有找到祖先。

• 举例1：
  
  

• 举例2：
  
  

完整代码如下

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 递归输入：根节点，p节点，q节点；递归输出：祖先节点
        # 结束条件
        if root == q or root == p or root == None:  # 找到等于q、p的节点后，返回
            return root
        
        # 单层递归逻辑
        # 层层返回，如果有值，就是祖先，如果为None，就是没有找到祖先
        left = self.lowestCommonAncestor(root.left, p, q)   
        right = self.lowestCommonAncestor(root.right, p, q)

		# 左、右存在（不为None）的前提是，左、右找到等于p、q的了
        if left and right:  # 如果左右都存在，说明找到公共祖先了，直接返回
            return root
        if left:  # 如果左存在，右不存在，说明左就是祖先
            return left
        return right  # 如果左不存在，就返回右（只能返回右了）
        # 此时，返回的右有两种情况：右不为None，找到祖先了；右为None，没有找到祖先。

235. 二叉搜索树的最近公共祖先

题目：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

👉示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
👉示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

题目分析

本题的二叉搜索树是有序的，要好好利用这个特点！

其实只要从上到下遍历的时候，cur节点是数值在[p, q]区间中，则说明该节点cur就是最近公共祖先了。

⭐️普通二叉树求最近公共祖先需要使用回溯，从底向上来查找。
⭐️二叉搜索树因为搜索树有序（相当于自带方向），那么只要从上向下遍历就可以了。

• 递归法递归的形式可以在return中给出：return self.lowestCommonAncestor(root.left, p, q)

• 迭代法在一定会找出答案的情况下，循环的条件是while True:

完整代码如下

利用和236一模一样的代码也可以AC。不过，本题从二叉搜索树有序的角度，重新写一个代码。

递归法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':      
        if root.val > p.val and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)  # `return`的方式进行递归
        elif root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

迭代法

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':    
        while True:  # 循环条件。因为一定会找到，所以`while True`
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                return root