当前没有测试数据。

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

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

输入格式

第一行，输入二叉树的结点，null表示空节点 。 第二行一个整数 $p$,表示节点 p。 第三行一个整数 $q$,表示节点 q。

输出格式

输出一行，p、q，最近公共祖先。

样例1

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

3

样例2

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

5

解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

提示：

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