树的存储与遍历

树由结点和边组成，除根结点外，每个结点恰有一个父结点。遍历就是按照规定顺序访问每个结点一次；它既能描述家族关系，也能用于表达递归调用、目录结构和搜索过程。

1. 常用存储方式

一般树常用邻接表保存孩子关系：g[u] 存放结点 u 的所有孩子或相邻结点，适合边数较少的情形。二叉树常用链式结点保存左右孩子；完全二叉树则可以用数组紧凑保存。

struct Node {
    int val;
    Node *left, *right;
    Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<vector<int>> children(n + 1); // 一般树的邻接表

若树以无向边输入，应在 DFS 中额外传入父结点 fa，避免沿原边走回父结点。

2. 二叉树的三种深度遍历

前序遍历顺序为“根—左—右”，适合先处理当前结点；中序遍历为“左—根—右”，二叉搜索树的中序结果递增；后序遍历为“左—右—根”，适合在得到子树信息后合并答案。

void preorder(Node* u) {
    if (!u) return;
    visit(u->val);                 // 根
    preorder(u->left);             // 左
    preorder(u->right);            // 右
}

void inorder(Node* u) {
    if (!u) return;
    inorder(u->left);
    visit(u->val);
    inorder(u->right);
}

void postorder(Node* u) {
    if (!u) return;
    postorder(u->left);
    postorder(u->right);
    visit(u->val);
}

3. 用栈和队列迭代遍历

递归本质上使用了调用栈。前序遍历可手动维护栈：先压右孩子、再压左孩子，左孩子才会先弹出。层序遍历使用队列，按深度从浅到深访问，是 BFS 在二叉树上的直接应用。

void preorderIter(Node* root) {
    if (!root) return;
    stack<Node*> st;
    st.push(root);
    while (!st.empty()) {
        Node* u = st.top(); st.pop();
        visit(u->val);
        if (u->right) st.push(u->right);
        if (u->left) st.push(u->left);
    }
}

void levelOrder(Node* root) {
    queue<Node*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        Node* u = q.front(); q.pop();
        visit(u->val);
        if (u->left) q.push(u->left);
        if (u->right) q.push(u->right);
    }
}

4. 复杂度与易错点

一次完整遍历会访问每个结点一次，时间复杂度为 O(n)。递归或深度遍历的栈空间为 O(h)，其中 h 是树高；退化成链时为 O(n)。层序遍历队列最坏可存放一层的所有结点，空间为 O(n)。

处理空树时应立即返回；无向树不要漏掉父结点判断；需要子树答案时应使用后序位置，在递归访问孩子之后再计算当前结点。