给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如,给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
*1.解题思路
用哈希表存储所有节点的父节点,然后利用节点的父节点信息从 p 、q开始不断往上查找。
接下来的问题在于根据哈希表找出公共子树。
假设:
1.根节点为root。公共子树为tree。两个子树为p和q。
2.p通过哈希表得到tree需要A步;q到tree需要B步;tree达到根节点需要C步
推得:
1.p到达tree需要A步;q到达tree需要B步。因为tree是未知的,所以并不确定A和B的值
2.但是p达到根节点之后,再从q的位置到达tree,需要A+C+B。同理,q需要B+C+A。这样需要的步数是相同的(具体是多少不需要知道)
3.两个子树运动了A+B+C步,此时的p和q相等。而这个位置就是tree。tree就是我们要的结果
2.源码