Problem1265--最近公共祖先

1265: 最近公共祖先

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 106  Solved: 41
[Submit] [Status] [Web Board] [Creator:]

Description

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

Input

输入两行。
第一行按照先序输入一棵二叉树,其中空节点用 -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

Source/Category