二叉树的最近公共祖先

给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
定义：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

题解思路

算法描述

本题采用递归的方法求解，核心思路如下：

Leetcode 49.二叉树的最近公共祖先-原题链接

题目内容

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

百度百科中最近公共祖先的定义为：“对于有根树$T$ 的两个节点 $p、q$，最近公共祖先表示为一个节点$x$，满足$x$ 是 $p、q$的祖先且 $x$的深度尽可能大（一个节点也可以是它自己的祖先）。”

输入描述

第一行包含二叉树的序列化数组，节点值之间用空格隔开，空节点用null表示。 第二行包含两个整数，表示节点 $p$ 和节点 $q$ 的值。

输出描述

输出最近公共祖先节点的值。

样例1

输入

3 5 1 6 2 0 8 null null 7 4
5 1

输出

3

说明

节点 $5$ 和节点 $1$ 的最近公共祖先是节点 $3$。

样例2

输入

3 5 1 6 2 0 8 null null 7 4
5 4

输出

5

样例3

输入

1 2
1 2

输出

1

提示

• 树中节点数目在范围 $[2, 10^5]$ 内。
• $-10^9 <= Node.val <= 10^9$
• 所有 $Node.val$ 互不相同。
• $p != q$
• $p$和 $q$ 均存在于给定的二叉树中。