二叉树的最近公共祖先
给定一个二叉树，找到该树中两个指定节点的最近公共祖先。
定义：对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
题解思路
算法描述
P4066.二叉树的最近公共祖先
LeetCode 236. 二叉树的最近公共祖先
题目描述
给定一棵二叉树的根节点 root，以及该树中的两个指定节点 p 和 q。
请找到节点 p 和节点 q 的最近公共祖先，并输出该祖先节点的值。
最近公共祖先的定义为：对于有根树 T 的两个节点 p 和 q，最近公共祖先表示为一个节点 x，满足 x 是 p 和 q 的祖先，并且 x 的深度尽可能大。
一个节点也可以是它自己的祖先。
输入描述
第一行输入若干个元素，表示二叉树的层序遍历结果。
相邻两个元素之间用一个空格隔开。
其中，整数表示节点值，null 表示空节点。
第二行输入两个整数 p 和 q，表示需要寻找最近公共祖先的两个节点值。
输出描述
输出一个整数，表示节点 p 和节点 q 的最近公共祖先节点的值。
样例 1
输入
3 5 1 6 2 0 8 null null 7 4
5 1
输出
3
样例解释
节点 5 和节点 1 的最近公共祖先是节点 3。
样例 2
输入
3 5 1 6 2 0 8 null null 7 4
5 4
输出
5
样例解释
节点 5 和节点 4 的最近公共祖先是节点 5。
因为根据定义，最近公共祖先节点可以为节点本身。
样例 3
输入
1 2
1 2
输出
1
数据范围
树中节点数目在 [2,105] 范围内。
−109<=Node.val<=109
所有 Node.val 互不相同。
p=q
p 和 q 均存在于给定的二叉树中。
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
