二叉树有前序，中序，后序三种遍历顺序。初学者很容易混淆。记住以下两个关键点就很好理解。
三种顺序的共同点：左右的顺序是不变的。
三种顺序的不同点：所谓的前中后序，说的是root节点的位置在前，中，后。先序是root,左,右；中序是左,root,右；后序的顺序是左，右，中。基于以上两点记忆就非常简单了。
递归序的后序遍历，即自定义的代码逻辑在左右递归结束后执行。通用的伪代码框架结构如下：
public static int recursion(TreeNode node){
if(node==null){
return 0;
}
//前序遍历
//代码逻辑
int left = recursion(node.left)；
//中序遍历 代码逻辑
int right = recursion(node.left)；
//后序遍历
//代码逻辑如下：
return left+right+node.data;
}
刚开始学递归，脑袋中一模拟方法中调用方法，脑袋就会炸锅，瞬间感觉脑细胞不够用了。其实可以换一个角度，放弃从root节点开始模拟，而是从最后一层叶子节点逆着模拟递归调用过程。
后序遍历从执行开始，代码到 int left = recursion(node.left) 部分就会开启新的压栈，这个过程一直会持续到什么时候呢？答案是最终的叶子节点。
如果现在的入参是叶子节点，则node.left =null ,node.right=null 那么执行递归函数后，都会返回0，即int left= 0，int right = 0；因为会判断入参为null,返回，不再继续开启新的堆栈了。
重点来了，跨过了前边两个坎儿
int left = recursion(node.left)；
int right = recursion(node.left)；
最终才会执行到 return left+right+node.data部分，也就是自定义代码这里。
叶子节点执行完了，因为第一次调用这个方法的都是int left = recursion(node.left)；所以会返回上一个堆栈记录的地址，接着执行上一个堆栈中的int right = recursion(node.left)；以此往复，最终回到根结点root 再次执行return left+right+node.data;
所以，后序遍历的难点就是，只有到了叶子节点部分，才会完整执行一次我们上边写的自定义代码。其他部分都是只开堆栈，不执行逻辑。
叶子节点时候，才会跳过左右继续递归这两个坎儿，第一次执行返回操作。其他高一层级的调用，都是大爷，懒得要死，儿子不干完活儿返回结果，你休想叫醒他，让他干一点活。但好处也是，一旦有返回结果了，他就自动执行了。这就是后序遍历的特点，高一级的依赖第低一级的返回结果。这么一说，有感觉了吧！
下边这张图展示了执行顺序
执行顺序图.png
从root节点开始，一直执行蓝色的，直到最后一个蓝色节点是null为止。返回到第二个蓝色节点，执行黄色点的递归方法，执行完后，返回到当前的节点，即倒数第二个蓝色节点，再返回，到达倒数第三个节点。。。以此类推
倒数第三个节点也是先执行蓝色，结束后回到黄色节点的方法体内，再执行红色递归调用，结束后再次回到黄色节点，执行黄色节点的自定义代码，之后再返回，达到倒数第三个节点
网友评论