判断二叉树节点祖先关系:前序和后序序列的应用
我们应该选择前序和后序序列来判断结点n1必定是结点n2的祖先。
判断方法如下:
-
根据前序序列找到结点n1和n2在二叉树T中的位置,并记录它们在前序序列中的位置。
-
根据后序序列,找到结点n1和n2在二叉树T中的位置,并记录它们在后序序列中的位置。
-
如果n1在n2的前面,且在前序序列中n1的位置在n2的左侧,同时在后序序列中n1的位置在n2的右侧,那么n1必定是n2的祖先。
注:以上判断方法基于二叉树中不存在相同的结点值。如果存在相同结点值,需要增加对结点的判断条件。
原文地址: https://www.cveoy.top/t/topic/nIXS 著作权归作者所有。请勿转载和采集!