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

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

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

百度百科中最近公共祖先的定义为：“对于有根树 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, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

通过次数77,958 | 提交次数119,846

Second Try

2020-09-20

参考题解得到的解法, 考虑到最近公共节点要么是p和q本身，要么是把p和q分别放在左右子树上这两种可能，使用递归法直接求解。

这个思路也还行，不过需要观察一下才能得到枚举判断。

如果p和q都大于root节点，那么说明公共节点在root右子树，反之在左子树。
如果p和q分别在root节点两边，那么说明这就是最近公共节点。
如果root等于p或者q，说明p和q中有一个就是父节点，也即最近公共节点。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
        最近公共节点，要么就是p点和q点之间有上下游关系，那么就是p点或q点本身；
        要么就是分别将p点和q点放置在左子树和右子树的那个点
        """
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        if (p.val > root.val and q.val < root.val) or (p.val < root.val and q.val > root.val):
            return root 
        # 公共节点就是自己
        if root == p or root == q:
            return root 

执行用时：104 ms, 在所有 Python3 提交中击败了44.23%的用户
内存消耗：17.3 MB, 在所有 Python3 提交中击败了60.49%的用户

First Try

2020-09-20

一开始还有点懵逼，感觉需要给所有点标记是否包含p和q，并且用广度优先遍历计算层级，得到最深的节点。这么一来需要操作的也太多了，而且并没有利用到二叉搜索树的特征，而且一看这还是easy级别的题目。

既然是二叉搜索树，那么可以很方便的从root节点找到目标节点，两个节点在路径上肯定有重叠的部分，比如至少是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':
        
        def search_path(node, target, path):
            """肯定存在，于是不用考虑None的问题"""
            path.append(node)
            if node.val == target.val:
                return 
            elif target.val > node.val:
                search_path(node.right, target, path)
            elif target.val < node.val:
                search_path(node.left, target, path)
        
        path_p, path_q = [], []
        search_path(root, p, path_p)
        search_path(root, q, path_q)
        
        # 第一位总归是root存在且相等
        for i in range(min(len(path_p), len(path_q))):
            if path_p[i].val != path_q[i].val:
                return path_p[i - 1]
        return path_p[i]  # 公共祖先为p或q
        

执行用时：92 ms, 在所有 Python3 提交中击败了89.21%的用户
内存消耗：=17.3 MB, 在所有 Python3 提交中击败了81.57%的用户