给定一棵二叉树和其中两个结点的值 p、q,返回它们的最近公共祖先结点(一个结点也可以是自己的祖先)。本题为「核心代码模式」:模板已内置层序数组建树与输出脚手架,只需补全指定函数。
第一行一个整数 n(1 ≤ n ≤ 10^4);第二行 n 个整数,按层序给出二叉树(-1 表示空结点,结点值为非负整数,保证根非空,-1 结点无子结点),且结点值互不相同;第三行两个整数 p、q(保证都在树中且 p ≠ q)。
一行,一个整数:最近公共祖先的结点值。