二叉树的最近公共祖先：ACM 模式刷题
按标准输入读取测试数据，输出结果后可在 CodeACM 在线运行和提交。
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入格式
第一行输入层序序列记号数 n 以及整数 p、q。
第二行输入包含整数和 null 的层序序列。
输出格式
输出节点 p 和 q 的最近公共祖先节点值。
数据范围
- 2 ≤ 节点数 ≤ 10⁵
- 所有节点值互不相同
- p 和 q 对应节点一定存在且不同
公开样例
样例 1
输入
11 5 1 3 5 1 6 2 0 8 null null 7 4
输出
3
节点 5 和 1 分别位于根节点 3 的两侧。
样例 2
输入
11 5 4 3 5 1 6 2 0 8 null null 7 4
输出
5
节点 5 是节点 4 的祖先。
练习建议
先根据输入输出格式写出可运行程序，再用公开样例检查结果；遇到边界情况时，补充自测用例后提交。