先序遍历二叉树

1. 定义二叉树节点结构

#include <iostream>
#include <vector>
#include <stack>
#include <utility>

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

2. 递归法

class Solution {
public:
    // 递归先序遍历
    std::vector<int> preorderRecursive(TreeNode* root) {
        std::vector<int> result;
        dfs(root, result);
        return result;
    }
    
private:
    void dfs(TreeNode* node, std::vector<int>& result) {
        if (!node) return;
        
        result.push_back(node->val);   // 访问根节点
        dfs(node->left, result);        // 遍历左子树
        dfs(node->right, result);       // 遍历右子树
    }
};

3. 迭代法（单栈法）

class Solution {
public:
    // 迭代先序遍历 - 使用栈
    std::vector<int> preorderIterative(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        std::stack<TreeNode*> stack;
        stack.push(root);
        
        while (!stack.empty()) {
            TreeNode* node = stack.top();
            stack.pop();
            
            result.push_back(node->val);  // 访问根节点
            
            // 注意：先右后左，因为栈是LIFO
            if (node->right) {
                stack.push(node->right);   // 右子节点先入栈（后访问）
            }
            if (node->left) {
                stack.push(node->left);    // 左子节点后入栈（先访问）
            }
        }
        
        return result;
    }
};

4. 迭代法（模拟递归过程）

class Solution {
public:
    // 模拟递归调用栈的迭代写法
    std::vector<int> preorderIterative2(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        // pair<节点, 是否已访问>
        std::stack<std::pair<TreeNode*, bool>> stack;
        stack.push({root, false});
        
        while (!stack.empty()) {
            auto [node, visited] = stack.top();
            stack.pop();
            
            if (!node) continue;
            
            if (visited) {
                result.push_back(node->val);  // 第二次遇到时访问
            } else {
                // 逆序入栈：右、左、根
                stack.push({node->right, false});
                stack.push({node->left, false});
                stack.push({node, true});      // 标记为已访问
            }
        }
        
        return result;
    }
};

5. 迭代法（手动模拟递归的另一种写法）

class Solution {
public:
    // 更接近递归思维的迭代写法
    std::vector<int> preorderIterative3(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> stack;
        TreeNode* current = root;
        
        while (current || !stack.empty()) {
            // 访问左子树直到最左边
            while (current) {
                result.push_back(current->val);  // 访问当前节点
                stack.push(current);              // 保存节点以便返回到右子树
                current = current->left;          // 移动到左子节点
            }
            
            // 回到父节点，转向右子树
            current = stack.top();
            stack.pop();
            current = current->right;
        }
        
        return result;
    }
};

复杂度分析

方法	时间复杂度	空间复杂度
递归	O(n)	O(h)，h为树高
迭代(标准)	O(n)	O(h)
迭代(模拟递归)	O(n)	O(h)
迭代(手动模拟)	O(n)	O(h)

要点说明

1. 标准迭代法：最简单直观，利用栈的LIFO特性

2. 模拟递归法：使用pair标记节点状态，代码模式通用

3. 手动模拟法：更接近递归的执行过程，适合理解递归本质

4. 栈溢出考虑：对于深度很大的树，递归可能导致栈溢出，应优先使用迭代法

中序遍历二叉树

1. 递归法

#include <iostream>
#include <vector>
#include <stack>

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

class Solution {
public:
    // 递归中序遍历
    std::vector<int> inorderRecursive(TreeNode* root) {
        std::vector<int> result;
        dfs(root, result);
        return result;
    }
    
private:
    void dfs(TreeNode* node, std::vector<int>& result) {
        if (!node) return;
        
        dfs(node->left, result);    // 遍历左子树
        result.push_back(node->val); // 访问根节点
        dfs(node->right, result);   // 遍历右子树
    }
};

2. 迭代法（单栈法）

class Solution {
public:
    // 迭代中序遍历 - 使用栈
    std::vector<int> inorderIterative(TreeNode* root) {
        std::vector<int> result;
        std::stack<TreeNode*> stack;
        TreeNode* current = root;
        
        while (current || !stack.empty()) {
            // 一直向左走到最左边
            while (current) {
                stack.push(current);
                current = current->left;
            }
            
            // 访问最左边的节点
            current = stack.top();
            stack.pop();
            result.push_back(current->val);
            
            // 转向右子树
            current = current->right;
        }
        
        return result;
    }
};

3. 迭代法（模拟递归过程）

class Solution {
public:
    // 模拟递归调用栈的迭代写法
    std::vector<int> inorderIterative2(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        // pair<节点, 是否已访问>
        std::stack<std::pair<TreeNode*, bool>> stack;
        stack.push({root, false});
        
        while (!stack.empty()) {
            auto [node, visited] = stack.top();
            stack.pop();
            
            if (!node) continue;
            
            if (visited) {
                result.push_back(node->val);  // 第二次遇到时访问
            } else {
                // 逆序入栈：右、根、左
                stack.push({node->right, false});
                stack.push({node, true});      // 标记为已访问
                stack.push({node->left, false});
            }
        }
        
        return result;
    }
};

4. 迭代法（颜色标记法-通用模板）

class Solution {
public:
    // 颜色标记法：0表示未访问，1表示已访问
    std::vector<int> inorderIterative3(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        std::stack<std::pair<TreeNode*, int>> stack;
        stack.push({root, 0});
        
        while (!stack.empty()) {
            auto [node, color] = stack.top();
            stack.pop();
            
            if (!node) continue;
            
            if (color == 0) {
                // 未访问：按逆序入栈（右、根、左）
                stack.push({node->right, 0});
                stack.push({node, 1});      // 标记为已访问
                stack.push({node->left, 0});
            } else {
                result.push_back(node->val);  // 已访问，输出
            }
        }
        
        return result;
    }
};

5. Morris遍历（空间复杂度O(1)）

class Solution {
public:
    // Morris中序遍历 - 空间复杂度O(1)
    std::vector<int> inorderMorris(TreeNode* root) {
        std::vector<int> result;
        TreeNode* current = root;
        
        while (current) {
            if (!current->left) {
                // 没有左子树，直接访问当前节点
                result.push_back(current->val);
                current = current->right;
            } else {
                // 找到左子树的最右节点（前驱节点）
                TreeNode* predecessor = current->left;
                while (predecessor->right && predecessor->right != current) {
                    predecessor = predecessor->right;
                }
                
                if (!predecessor->right) {
                    // 建立线索链接
                    predecessor->right = current;
                    current = current->left;
                } else {
                    // 已经访问过左子树，断开线索
                    predecessor->right = nullptr;
                    result.push_back(current->val);
                    current = current->right;
                }
            }
        }
        
        return result;
    }
};

复杂度分析

方法	时间复杂度	空间复杂度	优点	缺点
递归	O(n)	O(h)	代码简洁	可能栈溢出
标准迭代	O(n)	O(h)	安全可控	需要手动维护栈
模拟递归	O(n)	O(h)	通用模板	稍复杂
颜色标记	O(n)	O(h)	易于理解	额外状态标记
Morris	O(n)	O(1)	空间最优	会修改树结构

关键要点

1. 中序遍历特点：访问顺序是左子树 → 根节点 → 右子树

2. 标准迭代法：核心是"一直向左走"，使用栈保存路径

3. 与先序遍历的区别：

   • 先序遍历：访问节点后再压栈

   • 中序遍历：节点出栈时才访问

4. Morris遍历：利用线索二叉树思想，空间复杂度达到O(1)，但会临时修改树结构

5. 选择建议：日常用递归，深度大时用标准迭代，追求极致空间用Morris

后序遍历（左-右-根）的递归与迭代实现

1. 递归法

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>

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

class Solution {
public:
    // 递归后序遍历
    std::vector<int> postorderRecursive(TreeNode* root) {
        std::vector<int> result;
        dfs(root, result);
        return result;
    }
    
private:
    void dfs(TreeNode* node, std::vector<int>& result) {
        if (!node) return;
        
        dfs(node->left, result);    // 遍历左子树
        dfs(node->right, result);   // 遍历右子树
        result.push_back(node->val); // 访问根节点
    }
};

2. 迭代法（双栈法）

class Solution {
public:
    // 后序遍历迭代法 - 双栈法
    std::vector<int> postorderIterativeDoubleStack(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        std::stack<TreeNode*> stack1, stack2;
        stack1.push(root);
        
        // 第一个栈处理节点顺序：根-右-左
        while (!stack1.empty()) {
            TreeNode* node = stack1.top();
            stack1.pop();
            stack2.push(node);  // 将节点压入第二个栈
            
            // 注意：先左后右，因为第二个栈会反转顺序
            if (node->left) stack1.push(node->left);
            if (node->right) stack1.push(node->right);
        }
        
        // 第二个栈弹出顺序：左-右-根
        while (!stack2.empty()) {
            result.push_back(stack2.top()->val);
            stack2.pop();
        }
        
        return result;
    }
};

3. 迭代法（单栈法-需要记录访问状态）

class Solution {
public:
    // 后序遍历迭代法 - 单栈法（需要记录上次访问的节点）
    std::vector<int> postorderIterativeSingleStack(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        std::stack<TreeNode*> stack;
        TreeNode* current = root;
        TreeNode* lastVisited = nullptr;
        
        while (current || !stack.empty()) {
            // 一直向左走
            while (current) {
                stack.push(current);
                current = current->left;
            }
            
            // 查看栈顶节点
            current = stack.top();
            
            // 如果右子树为空或已经访问过，则访问当前节点
            if (!current->right || current->right == lastVisited) {
                result.push_back(current->val);
                stack.pop();
                lastVisited = current;
                current = nullptr;  // 重要：避免重复遍历
            } else {
                // 否则转向右子树
                current = current->right;
            }
        }
        
        return result;
    }
};

4. 迭代法（模拟递归过程）

class Solution {
public:
    // 模拟递归调用栈的迭代写法
    std::vector<int> postorderIterativeSimulate(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        // pair<节点, 是否已访问>
        std::stack<std::pair<TreeNode*, bool>> stack;
        stack.push({root, false});
        
        while (!stack.empty()) {
            auto [node, visited] = stack.top();
            stack.pop();
            
            if (!node) continue;
            
            if (visited) {
                result.push_back(node->val);  // 第二次遇到时访问
            } else {
                // 逆序入栈：根、右、左（因为栈是LIFO）
                stack.push({node, true});      // 标记为已访问
                stack.push({node->right, false});
                stack.push({node->left, false});
            }
        }
        
        return result;
    }
};

5. 迭代法（颜色标记法）

class Solution {
public:
    // 颜色标记法：0表示未访问，1表示已访问
    std::vector<int> postorderIterativeColor(TreeNode* root) {
        std::vector<int> result;
        if (!root) return result;
        
        std::stack<std::pair<TreeNode*, int>> stack;
        stack.push({root, 0});
        
        while (!stack.empty()) {
            auto [node, color] = stack.top();
            stack.pop();
            
            if (!node) continue;
            
            if (color == 0) {
                // 未访问：按逆序入栈（根、右、左）
                stack.push({node, 1});      // 标记为已访问
                stack.push({node->right, 0});
                stack.push({node->left, 0});
            } else {
                result.push_back(node->val);  // 已访问，输出
            }
        }
        
        return result;
    }
};

6. Morris后序遍历（空间复杂度O(1)）

class Solution {
public:
    // Morris后序遍历 - 需要反转输出
    std::vector<int> postorderMorris(TreeNode* root) {
        std::vector<int> result;
        TreeNode dummy(0);
        dummy.left = root;
        TreeNode* current = &dummy;
        
        while (current) {
            if (!current->left) {
                current = current->right;
            } else {
                // 找到左子树的最右节点（前驱节点）
                TreeNode* predecessor = current->left;
                while (predecessor->right && predecessor->right != current) {
                    predecessor = predecessor->right;
                }
                
                if (!predecessor->right) {
                    // 建立线索链接
                    predecessor->right = current;
                    current = current->left;
                } else {
                    // 已经访问过左子树，断开线索并输出左子树路径
                    predecessor->right = nullptr;
                    printReversePath(current->left, result);
                    current = current->right;
                }
            }
        }
        
        return result;
    }
    
private:
    // 反转输出从node到其最右节点的路径
    void printReversePath(TreeNode* node, std::vector<int>& result) {
        int count = 0;
        while (node) {
            result.push_back(node->val);
            node = node->right;
            count++;
        }
        // 反转这部分结果
        std::reverse(result.end() - count, result.end());
    }
};

关键要点

1. 后序遍历特点：访问顺序是左子树 → 右子树 → 根节点

2. 最难实现：因为根节点最后访问，无法像前序、中序那样简单处理

3. 双栈法：最直观，利用"根-右-左"反转得到"左-右-根"

4. 单栈法：需要记录上次访问的节点来判断右子树是否已访问

5. 通用模板：使用pair标记访问状态，适用于所有遍历方式

6. 选择建议：

   • 日常开发：递归法

   • 生产环境（树很深）：双栈法（简单可靠）

   • 追求空间效率：单栈法

   • 面试准备：掌握双栈法和单栈法

三种遍历方式对比

遍历方式	递归代码顺序	迭代难点	常用迭代方法
先序遍历	根-左-右	简单	单栈法
中序遍历	左-根-右	中等	单栈法
后序遍历	左-右-根	较难	双栈法/标记法

各方法复杂度对比

方法	时间复杂度	空间复杂度	优点	缺点
递归	O(n)	O(h)	代码最简洁	可能栈溢出
双栈法	O(n)	O(n)	直观易懂	需要两个栈
单栈法	O(n)	O(h)	空间较优	逻辑稍复杂
模拟递归	O(n)	O(h)	通用模板	需要状态标记
颜色标记	O(n)	O(h)	易于理解	额外状态
Morris	O(n)	O(1)	空间最优	实现复杂