内容简介：此文写给有7年交情的可爱的凌天小学弟～首先需要理解的是，前中后序遍历都是通过递归的方式，将后来需要用到的结点保存在栈中，比如下面这颗树：
此文写给有7年交情的可爱的凌天小学弟～
首先需要理解的是，前中后序遍历都是通过递归的方式，将后来需要用到的结点保存在栈中，比如下面这颗树：
如果是前序遍历，根左右，过程是：根节点m入栈并输出，访问m的左孩子a，a入栈并输出，访问a的左孩子c，c入栈并输出，c没有左孩子，无元素入栈，c没有右孩子，无元素入栈，c出栈，此时栈顶元素为a，访问a元素的右孩子d，d入栈并输出，d没有左孩子，无元素入栈，d没有右孩子，无元素入栈，d出栈，a左右子树都访问完了所以出栈， 现在栈顶元素是m， 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为止…
❤❤点击这里 -> 订阅PAT、蓝桥杯、GPLT天梯赛、LeetCode题解离线版❤❤以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
