后序遍历的递归算法核心思想是：按照“左子树 → 右子树 → 根节点”的顺序访问二叉树中的每个节点。以下是完整的C语言实现示例：
#include<stdio.h>#include<stdlib.h>// 二叉树节点定义typedefstructTreeNode{intdata;structTreeNode*lchild;structTreeNode*rchild;}TreeNode;// 后序遍历递归实现voidPostOrder(TreeNode*root){if(root!=NULL){PostOrder(root->lchild);// 遍历左子树PostOrder(root->rchild);// 遍历右子树printf("%d ",root->data);// 访问根节点}}关于三种遍历的路线逻辑，可以形象地理解为从根节点出发，沿二叉树外缘逆时针走一圈，每个节点会被经过三次：
- 第一次经过时访问 → 先序遍历（根左右）
- 第二次经过时访问 → 中序遍历（左根右）
- 第三次经过时访问 → 后序遍历（左右根）
时间复杂度分析：
由于每个节点仅被访问一次，无论哪种遍历方式，总时间复杂度均为O(n)。
空间复杂度分析：
主要消耗在系统调用栈上，取决于递归深度，即树的高度 h：
- 平均情况（平衡树）：O(log n)
- 最坏情况（单枝树，退化为链表）：O(n)
非递归遍历的基本思路是使用显式栈模拟函数调用栈的行为。以中序遍历为例，其非递归实现如下：
#include<stdbool.h>voidInOrderNonRecursive(TreeNode*root){TreeNode*stack[100];inttop=-1;TreeNode*p=root;while(p!=NULL||top!=-1){if(p!=NULL){stack[++top]=p;p=p->lchild;// 一直向左走}else{p=stack[top--];// 出栈printf("%d ",p->data);// 访问根p=p->rchild;// 转向右子树}}}对于后序遍历的非递归实现，较为复杂，通常需要记录前驱节点或使用标志位来判断是否已遍历完左右子树。
实现二叉树的后序遍历非递归算法的关键在于：在不使用递归的情况下，正确判断何时访问根节点。由于后序遍历是“左→右→根”，我们必须确保在访问根节点前，其左右子树都已处理完毕。
常用方法是使用一个栈来保存待处理的节点，并借助一个指针记录上一次访问的节点（prev），从而判断当前节点是否可以被访问。
✅ 后序遍历非递归算法（单栈 + 标记法）
#include<stdio.h>#include<stdlib.h>typedefstructTreeNode{intdata;structTreeNode*lchild;structTreeNode*rchild;}TreeNode;voidPostOrderNonRecursive(TreeNode*root){if(root==NULL)return;TreeNode*stack[100];// 模拟栈inttop=-1;TreeNode*prev=NULL;// 记录上一次访问的节点TreeNode*curr=root;while(curr!=NULL||top!=-1){// 一直走到最左边if(curr!=NULL){stack[++top]=curr;curr=curr->lchild;}else{// 查看栈顶元素（不弹出）curr=stack[top];// 如果右子树为空或已被访问过，则可以访问当前节点if(curr->rchild==NULL||curr->rchild==prev){printf("%d ",curr->data);top--;// 弹出栈prev=curr;// 更新已访问节点curr=NULL;// 当前节点置空，避免重复入栈}else{// 否则转向右子树curr=curr->rchild;}}}}🔍 算法逻辑说明：
- 入栈顺序：从根开始一路向左，将路径上的所有节点入栈。
- 判断访问时机：
- 若当前节点无右子树 → 可直接访问；
- 或右子树已经被访问过（
prev == curr->rchild）→ 表示左右子树均已处理，可访问根；
- 否则：转向右子树继续处理。
🧪 示例：
对于如下二叉树：
1 / \ 2 3 / \ 4 5后序遍历结果应为：4 5 2 3 1
该算法能正确输出此序列。
⏱️ 复杂度分析：
- 时间复杂度：O(n)，每个节点被压栈和弹栈一次。
- 空间复杂度：O(h)，h 为树的高度，最坏 O(n)，平均 O(log n)。
