leetcode原题链接：剑指 Offer 68 - II. 二叉树的最近公共祖先
代码思路：
递归查询两个节点p q，如果某个节点等于节点p或节点q，则返回该节点的值给父节点。
如果当前节点的左右子树分别包括p和q节点，那么这个节点必然是所求的解。
如果当前节点有一个子树的返回值为p或q节点，则返回该值。（告诉父节点有一个节点存在其子树中）
如果当前节点的两个子树返回值都为空，则返回空指针。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
if not root: return None
if root == p or root == q: return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: return root
return left if left else right复杂度分析
时间复杂度：
O
(
N
)
O(N)
O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为
O
(
N
)
O(N)
O(N)。
空间复杂度：
O
(
N
)
O(N)
O(N)，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为
O
(
N
)
O(N)
O(N)。