题解 | #农场牛群族谱#

• 题目考察的知识点 : 递归，二叉树的先序遍历
• 题目解答方法的文字分析：

1. 如果p和q中的任一个和root匹配，那么root就是最近公共祖先。
2. 如果都不匹配，则分别递归左、右子树。
3. 如果有一个节点出现在左子树，并且另一个节点出现在右子树，则root就是最近公共祖先.
4. 如果两个节点都出现在左子树，则说明最低公共祖先在左子树中，否则在右子树。
5. 继续递归左、右子树，直到遇到1或者3的情况。

• 本题解析所用的编程语言：Python
• 完整且正确的编程代码

# 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:
        if not root:
            return -1
        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)
        if left == -1:
            return right
        if right == -1:
            return left
        return root.val