5.10——236. 二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 例如,给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4] 5.10——236. 二叉树的最近公共祖先5.10——236. 二叉树的最近公共祖先     *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.源码 5.10——236. 二叉树的最近公共祖先5.10——236. 二叉树的最近公共祖先  
上一篇:数组中数字出现的次数


下一篇:Zhong__Git简单使用