【代码随想录day21】二叉搜索树的最近公共祖先

小小的香辛料

于 2023-07-27 17:08:16 发布

阅读量355

点赞数

分类专栏：代码随想录 LeetCode 数据结构文章标签： python 开发语言算法 leetcode

本文链接：https://blog.csdn.net/doubleguy/article/details/131964228

版权

LeetCode 同时被 3 个专栏收录

112 篇文章

订阅专栏

数据结构

97 篇文章

订阅专栏

代码随想录

61 篇文章

订阅专栏

该文章描述了一种算法问题，即在二叉树中找到两个给定节点的最低公共祖先。解决方案包括递归和迭代两种方法，关键在于比较当前节点值与目标节点值的关系来决定搜索方向。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目

思路

解题的关键是知道自顶向低递归遍历，第一次遇到root在p和q的区间中时，则root就是p和q的最近公共祖先节点。

递归法

# 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 not root:
            return 
        if root.val>p.val and root.val>q.val:
            left = self.lowestCommonAncestor(root.left, p, q)
            if left:
                return left

        if root.val<p.val and root.val<q.val:
            right = self.lowestCommonAncestor(root.right, p, q)
            if right:
                return right
        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 root:
            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