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

# 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 getPath(self, root: TreeNode, target:int)->List[int]:
        if root==None:
            return []
        
        path=[]
        node=root
        while target!=node.val:           
            if target<node.val:
                path.append(node.val)
                node=node.left
            elif target>node.val:
                path.append(node.val)
                node=node.right
                
        path.append(node.val)#while循环跳出时，说明target==node.val，要把node.val添进path
        return path
        
    #再比较两个目标节点路径上最近的共同节点    
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        path1=self.getPath(root,p)
        path2=self.getPath(root,q)
        minpathDepth=min(len(path1),len(path2))
        for i in range(minpathDepth):
            if path1[i]==path2[i]:
                res=path1[i]        
        return res

如果getPath这里想要递归调用，参考下面写法：

class Solution:
    def getPath(self, root: TreeNode, target:int, path=[]):        
        if root==None:
            return root
        else:
            ## path=[]如果添加，每次迭代都会更新path
            if target==root.val:
                path.append(root.val)
            elif target<root.val:
                path.append(root.val)
                self.getPath(root.left,target,path)
            elif target>root.val:
                path.append(root.val)
                self.getPath(root.right,target,path)
            return path

调用时写path1=self.getPath(root,p,[])。（ps:这里要采用把path作为一个自变量传入函数getPath中的做法。否则需要在代码里面添加初始化path=[]语句。这样会导致每次迭代会重新初始化一次，就达不到连续记录路径的目的了。