天梯赛爱考 字符串 和 树 以及 DFS、BFS

字符串前面写过了…字符串

树的建立

树的遍历（先序、中序、后序）

代码如下

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

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

// 前序遍历 - 递归
void preorderTraversalRecursive(TreeNode* root, std::vector<int>& result) {
    if (root == nullptr) return;
    result.push_back(root->val);
    preorderTraversalRecursive(root->left, result);
    preorderTraversalRecursive(root->right, result);
}

// 前序遍历 - 非递归
std::vector<int> preorderTraversalIterative(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) return result;
    std::stack<TreeNode*> stack;
    stack.push(root);
    while (!stack.empty()) {
        TreeNode* node = stack.top();
        stack.pop();
        result.push_back(node->val);
        if (node->right) stack.push(node->right);
        if (node->left) stack.push(node->left);
    }
    return result;
}

// 中序遍历 - 递归
void inorderTraversalRecursive(TreeNode* root, std::vector<int>& result) {
    if (root == nullptr) return;
    inorderTraversalRecursive(root->left, result);
    result.push_back(root->val);
    inorderTraversalRecursive(root->right, result);
}

// 中序遍历 - 非递归
std::vector<int> inorderTraversalIterative(TreeNode* root) {
    std::vector<int> result;
    std::stack<TreeNode*> stack;
    TreeNode* current = root;
    while (current != nullptr || !stack.empty()) {
        while (current != nullptr) {
            stack.push(current);
            current = current->left;
        }
        current = stack.top();
        stack.pop();
        result.push_back(current->val);
        current = current->right;
    }
    return result;
}

// 后序遍历 - 递归
void postorderTraversalRecursive(TreeNode* root, std::vector<int>& result) {
    if (root == nullptr) return;
    postorderTraversalRecursive(root->left, result);
    postorderTraversalRecursive(root->right, result);
    result.push_back(root->val);
}

// 后序遍历 - 非递归
std::vector<int> postorderTraversalIterative(TreeNode* root) {
    std::vector<int> result;
    if (root == nullptr) 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;
}

// 辅助函数：打印结果
void printResult(const std::vector<int>& result) {
    for (int val : result) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

int main() {
    // 构建一个简单的二叉树
    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);

    std::vector<int> result;

    // 前序遍历
    std::cout << "Preorder Traversal (Recursive): ";
    preorderTraversalRecursive(root, result);
    printResult(result);
    result.clear();

    std::cout << "Preorder Traversal (Iterative): ";
    result = preorderTraversalIterative(root);
    printResult(result);
    result.clear();

    // 中序遍历
    std::cout << "Inorder Traversal (Recursive): ";
    inorderTraversalRecursive(root, result);
    printResult(result);
    result.clear();

    std::cout << "Inorder Traversal (Iterative): ";
    result = inorderTraversalIterative(root);
    printResult(result);
    result.clear();

    // 后序遍历
    std::cout << "Postorder Traversal (Recursive): ";
    postorderTraversalRecursive(root, result);
    printResult(result);
    result.clear();

    std::cout << "Postorder Traversal (Iterative): ";
    result = postorderTraversalIterative(root);
    printResult(result);

    // 释放内存
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}  

dfs、bfs暂时不出了，需要沉淀....