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

Difficulty
easy
Tags
二叉树
二叉搜索树
URL
https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
Star
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
notion imagenotion image
示例 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, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

法1 递归法

思路
  1. 把二叉搜索树当作普通二叉树来遍历，参考
    🎱
    236. 二叉树的最近公共祖先
  1. 利用二叉搜索树的性质，左小右大。天然的自带方向，只要从上往下遍历即可。
      2. 遍历的时候，如果当前节点的值cur.val 在p 和q的区间中就可以说明cur节点为公共节点。
题解
# 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 is None:
            return None
        # 如果当前节点的值小于 p 和 q ，那么向左子树递归
        if root.val > p.val and root.val > q.val:
            left = self.lowestCommonAncestor(root.left, p, q)
            if left:
                return left
        # 如果当前节点的值大于 p 和 q 的值，那么向右子树递归
        if root.val < p.val and root.val < q.val:
            right = self.lowestCommonAncestor(root.right, p, q)
            if right :
                return right
        # 否则当前节点值在 p 和 q 之间 ，返回当前节点即可
        return root

法2 迭代法

思路
遍历的时候利用二叉搜索树的性质，左小右大。天然的自带方向，只要从上往下遍历。
  • 如果当前节点的值cur.val 在p 和q的区间中就可以说明cur节点为公共节点。
题解
# 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':
        
        stack = []
        stack.append(root)
        while len(stack) > 0:
            node = stack.pop()
            # 如果当前节点的值 在[p.val,q.val] 之中
            if p.val >= node.val >= q.val or q.val >= node.val >= p.val:
                return node
            # 如果当前节点的值大于 p 和 q 的值 去左边
            if node.val > p.val and node.val > q.val and node.left:
                stack.append(node.left)
            # 如果当前节点的值小于于 p 和 q 的值 去右边
            if node.val < p.val and node.val < q.val and node.right:
                stack.append(node.right)
可以不用stack，直接在二叉搜索树上查找。
此外，因为题目说了一定有，所以可以这样查找，不然，还需要判断是否不存在的情况
# 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.right
            elif root.val > p.val and root.val > q.val:
                root = root.left
            else:
                return root
        return None