1265: 最近公共祖先
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 934 Solved: 461
[Submit] [Status] [Web Board] [Creator:]
Description
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
Input
输入两行。
第一行按照先序输入一棵二叉树，其中空节点用 -1 表示。
第二行输入两个结点的值val1, val2 , 输出该结点的双亲节点的val.(数据保证所有节点val的值都不相同)
第一行按照先序输入一棵二叉树，其中空节点用 -1 表示。
第二行输入两个结点的值val1, val2 , 输出该结点的双亲节点的val.(数据保证所有节点val的值都不相同)
Output
输出一行，代表最近公共祖先的val。
Sample Input
3 5 6 -1 -1 2 7 -1 -1 4 -1 -1 1 0 -1 -1 8 -1 -1
5 1
Sample Output
3