在二叉树中有两个结点m和n,若m是n的祖先,则使用后序遍历可以找到从m到n的路径

此文写给有7年交情的可爱的凌天小学弟~

首先需要理解的是,前中后序遍历都是通过递归的方式,将后来需要用到的结点保存在栈中,比如下面这颗树:

如果是前序遍历,根左右,过程是:根节点m入栈并输出,访问m的左孩子a,a入栈并输出,访问a的左孩子c,c入栈并输出,c没有左孩子,无元素入栈,c没有右孩子,无元素入栈,c出栈,此时栈顶元素为a,访问a元素的右孩子d,d入栈并输出,d没有左孩子,无元素入栈,d没有右孩子,无元素入栈,d出栈,a左右子树都访问完了所以出栈,现在栈顶元素是m,m已经没有作用了所以出栈,访问m的右孩子b,m的右孩子b入栈并输出,接着访问b的左孩子e,e入栈并输出……

如果中序遍历,左根右,过程是:根节点m入栈,访问m的左孩子,所以m的左孩子a入栈,访问a的左孩子,所以a的左孩子c入栈,c没有左孩子,c现在输出并出栈,c没有右孩子所以没有元素入栈,现在栈顶元素是a,a输出并出栈,a的右孩子d入栈,此时d没有左孩子所以没有元素入栈,d输出并出栈,d没有右孩子所以没有元素入栈,现在栈顶元素是m,m输出,此时m已经没有作用了所以出栈,m的右孩子b入栈,访问b的左孩子,所以b的左孩子e入栈……

所以在前序和中序的过程中,如果n在m的右子树部分,遍历过程中找到了n,但是m已经不在栈中,因为栈中只会保留等会需要用到的e和b结点,而m已经完成了访问根结点和m的左子树的任务,已经被出栈,所以无法追溯n如何走到m

但是后序遍历就不一样啦,后序的顺序是左右根,所以只要m的左右子树还没遍历完成,m就不能出栈,在遍历m的左右子树过程中,无论在m的左边还是右边找到了n,都可以直接返回然后根据栈中的路径让n找到回到m的路,这样就能找到m到n的路径~

所以一旦n在m的右子树,且离的较远,m就会在前序和中序的过程中因为已经完成了访问左、访问根的任务,而被栈遗忘,让找到了n的时候也不知怎么回到m……而只有后序会让作为祖先(子树的根)的m永远被铭记直到n找到m为止…