C++算法（树算法）

1. 二叉树的前序、中序、后序遍历

思路解析：

• 前序遍历（Pre-order）：根 -> 左 -> 右
• 中序遍历（In-order）：左 -> 根 -> 右
• 后序遍历（Post-order）：左 -> 右 -> 根
• 可以用递归或迭代（栈）实现
• 时间复杂度：O(N)，空间复杂度：O(H)，H 为树的高度

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

using namespace std;

// 二叉树节点定义
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// ========== 递归实现 ==========

// 前序遍历：根 -> 左 -> 右
void preorderRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    
    result.push_back(root->val);      // 访问根节点
    preorderRecursive(root->left, result);   // 遍历左子树
    preorderRecursive(root->right, result);  // 遍历右子树
}

// 中序遍历：左 -> 根 -> 右
void inorderRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    
    inorderRecursive(root->left, result);    // 遍历左子树
    result.push_back(root->val);      // 访问根节点
    inorderRecursive(root->right, result);   // 遍历右子树
}

// 后序遍历：左 -> 右 -> 根
void postorderRecursive(TreeNode* root, vector<int>& result) {
    if (root == nullptr) return;
    
    postorderRecursive(root->left, result);  // 遍历左子树
    postorderRecursive(root->right, result); // 遍历右子树
    result.push_back(root->val);      // 访问根节点
}

// ========== 迭代实现（使用栈）==========

// 前序遍历（迭代）
vector<int> preorderIterative(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st;
    st.push(root);
    
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        result.push_back(node->val);
        
        // 先压右子树，再压左子树（栈是后进先出）
        if (node->right) st.push(node->right);
        if (node->left) st.push(node->left);
    }
    
    return result;
}

// 中序遍历（迭代）
vector<int> inorderIterative(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* curr = root;
    
    while (curr != nullptr || !st.empty()) {
        // 一直往左走，将所有左节点入栈
        while (curr != nullptr) {
            st.push(curr);
            curr = curr->left;
        }
        
        // 访问栈顶节点
        curr = st.top();
        st.pop();
        result.push_back(curr->val);
        
        // 转向右子树
        curr = curr->right;
    }
    
    return result;
}

// 后序遍历（迭代）
vector<int> postorderIterative(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    
    stack<TreeNode*> st1, st2;
    st1.push(root);
    
    // 使用两个栈，第一个栈按 根->右->左 的顺序
    // 第二个栈反转后就是 左->右->根
    while (!st1.empty()) {
        TreeNode* node = st1.top();
        st1.pop();
        st2.push(node);
        
        if (node->left) st1.push(node->left);
        if (node->right) st1.push(node->right);
    }
    
    // 从第二个栈中取出结果
    while (!st2.empty()) {
        result.push_back(st2.top()->val);
        st2.pop();
    }
    
    return result;
}

int main() {
    // 构建测试树
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    // 递归遍历
    vector<int> preorder, inorder, postorder;
    preorderRecursive(root, preorder);
    inorderRecursive(root, inorder);
    postorderRecursive(root, postorder);
    
    cout << "前序遍历（递归）: ";
    for (int val : preorder) cout << val << " ";
    cout << endl;
    
    cout << "中序遍历（递归）: ";
    for (int val : inorder) cout << val << " ";
    cout << endl;
    
    cout << "后序遍历（递归）: ";
    for (int val : postorder) cout << val << " ";
    cout << endl;
    
    // 迭代遍历
    cout << "\n前序遍历（迭代）: ";
    vector<int> preorderIter = preorderIterative(root);
    for (int val : preorderIter) cout << val << " ";
    cout << endl;
    
    cout << "中序遍历（迭代）: ";
    vector<int> inorderIter = inorderIterative(root);
    for (int val : inorderIter) cout << val << " ";
    cout << endl;
    
    cout << "后序遍历（迭代）: ";
    vector<int> postorderIter = postorderIterative(root);
    for (int val : postorderIter) cout << val << " ";
    cout << endl;
    
    return 0;
}

2. 判断一个二叉树是否是平衡二叉树

思路解析：

• 平衡二叉树：每个节点的左右子树高度差不超过 1
• 递归判断：对于每个节点，检查左右子树是否平衡，且高度差 ≤ 1
• 优化：在计算高度的同时判断是否平衡，避免重复计算
• 时间复杂度：O(N)

#include <iostream>
#include <algorithm>

using namespace std;

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

// 辅助函数：计算高度并判断是否平衡
// 返回 -1 表示不平衡，否则返回高度
int checkHeight(TreeNode* root) {
    if (root == nullptr) return 0;  // 空树高度为 0
    
    // 递归检查左子树
    int leftHeight = checkHeight(root->left);
    if (leftHeight == -1) return -1;  // 左子树不平衡
    
    // 递归检查右子树
    int rightHeight = checkHeight(root->right);
    if (rightHeight == -1) return -1;  // 右子树不平衡
    
    // 检查当前节点的左右子树高度差
    if (abs(leftHeight - rightHeight) > 1) {
        return -1;  // 高度差超过 1，不平衡
    }
    
    // 返回当前节点的高度
    return max(leftHeight, rightHeight) + 1;
}

// 判断是否为平衡二叉树
bool isBalanced(TreeNode* root) {
    return checkHeight(root) != -1;
}

int main() {
    // 测试 1：平衡二叉树
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode* root1 = new TreeNode(1);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(3);
    root1->left->left = new TreeNode(4);
    root1->left->right = new TreeNode(5);
    
    cout << "测试 1: " << (isBalanced(root1) ? "是平衡二叉树" : "不是平衡二叉树") << endl;
    
    // 测试 2：不平衡二叉树
    //       1
    //      /
    //     2
    //    /
    //   3
    TreeNode* root2 = new TreeNode(1);
    root2->left = new TreeNode(2);
    root2->left->left = new TreeNode(3);
    
    cout << "测试 2: " << (isBalanced(root2) ? "是平衡二叉树" : "不是平衡二叉树") << endl;
    
    return 0;
}

3. 二叉树的最大深度

思路解析：

• 最大深度：从根节点到最远叶子节点的最长路径上的节点数
• 递归：最大深度 = max(左子树深度, 右子树深度) + 1
• 时间复杂度：O(N)

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

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

// ========== 递归实现 ==========
int maxDepthRecursive(TreeNode* root) {
    if (root == nullptr) return 0;  // 空树深度为 0
    
    // 递归计算左右子树的最大深度
    int leftDepth = maxDepthRecursive(root->left);
    int rightDepth = maxDepthRecursive(root->right);
    
    // 返回较大的深度 + 1（当前节点）
    return max(leftDepth, rightDepth) + 1;
}

// ========== 迭代实现（层次遍历）==========
int maxDepthIterative(TreeNode* root) {
    if (root == nullptr) return 0;
    
    queue<TreeNode*> q;
    q.push(root);
    int depth = 0;
    
    while (!q.empty()) {
        int levelSize = q.size();  // 当前层的节点数
        depth++;  // 深度加 1
        
        // 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    
    return depth;
}

int main() {
    // 构建测试树
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    cout << "最大深度（递归）: " << maxDepthRecursive(root) << endl;
    cout << "最大深度（迭代）: " << maxDepthIterative(root) << endl;
    
    return 0;
}

4. 二叉树的最小深度

思路解析：

• 最小深度：从根节点到最近叶子节点的最短路径上的节点数
• 注意：叶子节点是指没有子节点的节点
• 递归时需要特别处理只有一个子树的情况
• 时间复杂度：O(N)

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

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

// ========== 递归实现 ==========
int minDepthRecursive(TreeNode* root) {
    if (root == nullptr) return 0;
    
    // 如果左子树为空，只计算右子树
    if (root->left == nullptr) {
        return minDepthRecursive(root->right) + 1;
    }
    
    // 如果右子树为空，只计算左子树
    if (root->right == nullptr) {
        return minDepthRecursive(root->left) + 1;
    }
    
    // 左右子树都存在，取较小的深度
    int leftDepth = minDepthRecursive(root->left);
    int rightDepth = minDepthRecursive(root->right);
    
    return min(leftDepth, rightDepth) + 1;
}

// ========== 迭代实现（BFS 层次遍历）==========
int minDepthIterative(TreeNode* root) {
    if (root == nullptr) return 0;
    
    queue<TreeNode*> q;
    q.push(root);
    int depth = 1;
    
    while (!q.empty()) {
        int levelSize = q.size();
        
        // 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            
            // 如果是叶子节点，直接返回当前深度
            if (node->left == nullptr && node->right == nullptr) {
                return depth;
            }
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        depth++;
    }
    
    return depth;
}

int main() {
    // 测试树
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    cout << "最小深度（递归）: " << minDepthRecursive(root) << endl;
    cout << "最小深度（迭代）: " << minDepthIterative(root) << endl;
    
    return 0;
}

5. 二叉树的层次遍历

思路解析：

• 层次遍历（Level Order Traversal）：按层从上到下、从左到右访问节点
• 使用队列（BFS）实现
• 可以返回每一层的节点值
• 时间复杂度：O(N)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

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

// 层次遍历，返回每一层的节点值
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();  // 当前层的节点数
        vector<int> currentLevel;  // 存储当前层的节点值
        
        // 遍历当前层的所有节点
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel.push_back(node->val);
            
            // 将下一层的节点加入队列
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        result.push_back(currentLevel);
    }
    
    return result;
}

// 之字形层次遍历（Zigzag Level Order）
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (root == nullptr) return result;
    
    queue<TreeNode*> q;
    q.push(root);
    bool leftToRight = true;  // 标记遍历方向
    
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel(levelSize);
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front();
            q.pop();
            
            // 根据方向决定插入位置
            int index = leftToRight ? i : (levelSize - 1 - i);
            currentLevel[index] = node->val;
            
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        
        result.push_back(currentLevel);
        leftToRight = !leftToRight;  // 切换方向
    }
    
    return result;
}

int main() {
    // 构建测试树
    //       3
    //      / \
    //     9  20
    //       /  \
    //      15   7
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);
    
    // 普通层次遍历
    cout << "层次遍历:" << endl;
    vector<vector<int>> levels =