讨论/算法和数据结构/判断⼆叉树中结点是否存在祖孙关系/
判断⼆叉树中结点是否存在祖孙关系

判断以 root 为根的⼆叉树中结点 a 和结点 b 是否存在祖孙关系,若存在 祖孙关系,则输出其祖先到⼦孙之间的路径。

展开讨论

做一次dfs,记录结点的父亲结点和位于第几层。假设结点a位于L(a)层,结点b位于L(b)层,L(a)>=L(b)L(a) >= L(b),那么从结点a开始向上遍历,遍历到结点a的祖先中位于L(b)层的结点,如果这个就是b,那么b就是a的祖先,如果不是,那么这倆结点没有祖孙关系

  1. 如果题目只需要查询一组a和b,那么就是上面分析的做法,复杂度是o(n)
  2. 如果题目需要查询多组a和b,那么上面分析的做法以外,还要做一次倍增算法,就是每个结点,预处理这个结点的第1个祖先,第2个祖先,第4个祖先,第8个祖先。。。。以便可以用log(h)的复杂度查询结点a和结点b是否祖孙关系
展开全部 3 讨论