二叉树——二叉树的最近公共祖先

二叉树的最近公共祖先
前言题目思路代码结论

前言
解决公共祖先问题时我想到的办法时两次遍历，分别在树tree中遍历p和q，
两次的遍历中从根到目标节点的路径节点指针的值分别保存到集合和队列中，
在队列出队时只要在集合中出现过，那他就是最近公共祖先。
这个方法也能AC。但是时间和空间消耗巨大。
借鉴了一下精选接法，才明白对于二叉树的递归还是内有熟练应用。

题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

解释：节点 5 和节点 1 的最近公共祖先是节点

二叉树——二叉树的最近公共祖先最先出现在Python成神之路。