给定一个二叉树,要求找到该树中指定节点 p、q 的最近公共祖先:

最近公共祖先:对于树的两个节点 p、q,最近公共祖先表示为一个节点 lca_node,满足 lca_node 是 p、q 的祖先且 lca_node 的深度尽可能大(一个节点也可以是自己的祖先)。

下面递归求解 lca_node。递归需要满足以下条件:

如果 p、q 只有一个存在,则返回存在的一个。

如果 p、q 都不存在,则返回存在的一个。

具体思路为:

递归遍历左子树、右子树,并判断左右子树结果。

如果左右子树都不为空,则说明 p、q 在当前根节点的两侧,当前根节点就是他们的最近公共祖先。

如果左右子树都为空,则返回空。