
思路
如果当前节点是目标节点p,则无论q点在其左子树还是右子树,p均为最近公共祖先
如果目标节点分别在节点的左子树和右子树各一,则当前节点为最近公共祖先,故我们要判断的是左右子树上是否存在,如果存在则将根节点标记为公共祖先,故使用后根遍历法,该方式允许我们收集左右子树的信息,并对根节点做处理
实现

思路
如果当前节点是目标节点p,则无论q点在其左子树还是右子树,p均为最近公共祖先
如果目标节点分别在节点的左子树和右子树各一,则当前节点为最近公共祖先,故我们要判断的是左右子树上是否存在,如果存在则将根节点标记为公共祖先,故使用后根遍历法,该方式允许我们收集左右子树的信息,并对根节点做处理
实现
本文标题:深度优先遍历--二叉树的最近公共祖先
本文链接:https://www.haomeiwen.com/subject/obhalrtx.html
网友评论