说后序位置之前，先简单说下中序和前序。
中序位置主要用在 BST 场景中，你完全可以把 BST 的中序遍历认为是遍历有序数组。
前序位置本身其实没有什么特别的性质，之所以你发现好像很多题都是在前序位置写代码，实际上是因为我们习惯把那些对前中后序位置不敏感的代码写在前序位置罢了。
你可以发现，前序位置的代码执行是自顶向下的，而后序位置的代码执行是自底向上的：
前序遍历： 1，2，3，4，5，6，7
后序遍历：3，4，2，7，6，5，1
中序遍历：3，2，4，1，7，6，5
不会看这篇 （必看！画的真好呜呜呜） 二叉树三种遍历（动态图 + 代码深入理解）
这不奇怪，因为本文开头就说了前序位置是刚刚进入节点的时刻，后序位置是即将离开节点的时刻。
但这里面大有玄妙，意味着前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。
Hint
举具体的例子，现在给你一棵二叉树，我问你两个简单的问题：
1、如果把根节点看做第 1 层，如何打印出每一个节点所在的层数？
2、如何打印出每个节点的左右子树各有多少节点？
第一个问题可以这样写代码：
// 二叉树遍历函数
void traverse(TreeNode root, int level) {
if (root == null) {
return;
}
// 前序位置
printf("节点 %s 在第 %d 层", root, level);
traverse(root.left, level + 1);
traverse(root.right, level + 1);
}
// 这样调用
traverse(root, 1);
第二个问题可以这样写代码：
// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
if (root == null) {
return 0;
}
int leftCount = count(root.left);
int rightCount = count(root.right);
// 后序位置
printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
root, leftCount, rightCount);
return leftCount + rightCount + 1;
}
好好细读上面的两个问题，观察前序与后序位置的特殊之处
这两个问题的根本区别在于：一个节点在第几层，你从根节点遍历过来的过程就能顺带记录，用递归函数的参数就能传递下去；而以一个节点为根的整棵子树有多少个节点，你需要遍历完子树之后才能数清楚，然后通过递归函数的返回值拿到答案。
结合这两个简单的问题，你品味一下后序位置的特点，只有后序位置才能通过返回值获取子树的信息。
那么换句话说，一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
接下来看下后序位置是如何在实际的题目中发挥作用的，简单聊下力扣第 543 题「二叉树的直径」，让你计算一棵二叉树的最长直径长度。
所谓二叉树的「直径」长度，就是任意两个结点之间的路径长度。最长「直径」并不一定要穿过根结点，比如下面这棵二叉树：
它的最长直径是 3，即 [4,2,1,3]，[4,2,1,9] 或者 [5,2,1,3] 这几条「直径」的长度。
解决这题的关键在于，每一条二叉树的「直径」长度，就是一个节点的左右子树的最大深度之和。
现在让我求整棵树中的最长「直径」，那直截了当的思路就是遍历整棵树中的每个节点，然后通过每个节点的左右子树的最大深度算出每个节点的「直径」，最后把所有「直径」求个最大值即可。
最大深度的算法我们刚才实现过了，上述思路就可以写出以下代码：
class Solution {
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 对每个节点计算直径，求最大直径
traverse(root);
return maxDiameter;
}
// 遍历二叉树
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 对每个节点计算直径
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
int myDiameter = leftMax + rightMax;
// 更新全局最大直径
maxDiameter = Math.max(maxDiameter, myDiameter);
traverse(root.left);
traverse(root.right);
}
// 计算二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
return 1 + Math.max(leftMax, rightMax);
}
}
这个解法是正确的，但是运行时间很长，原因也很明显，traverse 遍历每个节点的时候还会调用递归函数 maxDepth，而 maxDepth 是要遍历子树的所有节点的，所以最坏时间复杂度是 O(N^2)。
这就出现了刚才探讨的情况，前序位置无法获取子树信息，所以只能让每个节点调用 maxDepth 函数去算子树的深度。
那如何优化？我们应该把计算「直径」的逻辑放在后序位置，准确说应该是放在 maxDepth 的后序位置，因为 maxDepth 的后序位置是知道左右子树的最大深度的。
所以，稍微改一下代码逻辑即可得到更好的解法：
class Solution {
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置，顺便计算最大直径
int myDiameter = leftMax + rightMax;
maxDiameter = Math.max(maxDiameter, myDiameter);
return 1 + Math.max(leftMax, rightMax);
}
}
这下时间复杂度只有 maxDepth 函数的 O(N) 了。
讲到这里，照应一下前文：遇到子树问题，首先想到的是给函数设置返回值，然后在后序位置做文章。
Info
思考题：请你思考一下，运用后序遍历的题目使用的是「遍历」的思路还是「分解问题」的思路？
反过来，如果你写出了类似一开始的那种递归套递归的解法，大概率也需要反思是不是可以通过后序遍历优化了。