描述:给定一个二叉树的根节点 root,以及二叉树中两个节点 p 和 q。
要求:找到该二叉树中指定节点 p、q 的最近公共祖先。
最近公共祖先:对于树的两个节点 p、q,最近公共祖先表示为一个节点 lca_node,满足 lca_node 是 p、q 的祖先且 lca_node 的深度尽可能大(一个节点也可以是自己的祖先)。
p 和 q 均存在于给定的二叉树中。
因为根据定义最近公共祖先节点可以为节点本身。
下面递归求解 lca_node。递归需要满足以下条件:
如果 p、q 只有一个存在,则返回存在的一个。
具体思路为:
如果当前节点 node 不为 None,则递归遍历左子树、右子树,并判断左右子树结果。
如果左右子树都不为空,则说明 p、q 在当前根节点的两侧,当前根节点就是他们的最近公共祖先。
如果左右子树都为空,则返回 None。