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

思路：同样可以采取二叉树最近公共祖先的算法

1、深度优先遍历dfs，判断当前节点是否为o1、o2，先找到的必为祖先

2、递归左右子树

• 左右子树中均分布o1、o2，则公共祖先为当前节点

• 均在左，则返回左，均在右，则返回右

注意：

此题有一个小坑，由于存在值为0的val，所以不能用not root判断无结果返回

class Solution:
    def lowestCommonAncestor(self , root: TreeNode, p: int, q: int) -> int:
        if not root:
            return
        
        if root.val == p or root.val == q:
            return root.val
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        print(root.val, left, right)
        
        if left != None and right != None: # 小坑! 不能用not left and not right
            return root.val
        if not right:
            return left
        if not left:
            return right