题解 | #二叉搜索树的最近公共祖先#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param p int整型 
# @param q int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        # write code here
        # 找二叉树公共节点，一般就是记录路径然后找最后一个相等的元素
        path1 = []
        path2 = []
        if root==None:
            return None
        self.find(root,path1,p)
        self.find(root,path2,q)
        i = 0
        res = 0
        while i<len(path1) and i <len(path2):
            # 如果路径相等的话就继续
            if path1[i] == path2[i]:
                res = path1[i]
                i+=1
            else:
                break
            
        return res
            
    
    def find(self,root:TreeNode,path:list,n:int):
        # 建议不要直接对传入参数操作，除非你想对它进行修改改变
        cur = root
        while cur.val!=n and cur:
            path.append(cur.val)
            if n>cur.val:
                cur = cur.right
            else:
                cur = cur.left
        # 这题最后要把自己这个节点也加上
        path.append(cur.val)

• step 1：根据二叉搜索树的性质，从根节点开始查找目标节点，当前节点比目标小则进入右子树，当前节点比目标大则进入左子树，直到找到目标节点。这个过程成用数组记录遇到的元素。
• step 2：分别在搜索二叉树中找到p和q两个点，并记录各自的路径为数组。
• step 3：同时遍历两个数组，比较元素值，最后一个相等的元素就是最近的公共祖先。