算法题:二叉树的最近公共祖先

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

对于树的遍历：

• 使用递归是一种高效、简便的方式，不要怕使用递归。
• 对于二叉树的递归又分为三种不同的形式，分别是前序、中序、后序。
• 如果面试要求不使用递归，则可以使用循环解法。

各种顺序的节点遍历顺序：

• 前序：根左右
• 中序：左根右
• 后序：左右根

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        # 如果 root 为空或者
        # 如果 p 和 q 中某一个等于 root（其本身为最近公共祖先）
        # 直接返回 root 为结果
        if not root or root == p or root == q:
            return root

        # 进行先序遍历，根左右
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if not left:
            return right
        if not right:
            return left

        return root