后序遍历

后序遍历是：先左子树，再右子树，最后才轮到自己。这在"必须先算完孩子才能算自己"的任务里特别好用。比如算一个文件夹有多大，得先把里面每个子文件夹都量完，最后把它们加起来再算上自己。

#include <iostream>
using namespace std;
struct Node { int val; Node* l; Node* r; };
int sum(Node* p) {
    if (!p) return 0;
    int a = sum(p->l);   // 先左
    int b = sum(p->r);   // 再右
    return a + b + p->val; // 最后加自己
}
int main() {
    Node l{3,0,0}, r{5,0,0}, root{2,&l,&r};
    cout << sum(&root); // 输出：10
}

容易搞混：如果先加自己再去算孩子，孩子还没算出来，结果就是错的。后序的关键就是"自己一定排在最后"。