对于二叉树T的两个结点n1和n2我们应该选择二叉树T结点的前序、中序和后序中哪两个序列来判断结点n1必定是结点n2的祖先试给出判断的方法。不需证明判断方法的正确性
我们应该选择二叉树T的前序和中序序列来判断结点n1必定是结点n2的祖先。
判断方法:
-
首先,根据前序序列,找到n1和n2在二叉树中的位置。
-
接着,根据中序序列,找到n1和n2在二叉树中的位置。
-
如果n1在n2的左子树或右子树中,则n1必定是n2的祖先。
-
如果n1和n2分别在中序序列中的左子树或右子树中,则需要继续递归判断左子树和右子树。
-
如果n1和n2在中序序列中分别位于某个结点的左右子树中,则该结点必定是n1和n2的最近公共祖先。
原文地址: https://www.cveoy.top/t/topic/dxDf 著作权归作者所有。请勿转载和采集!