如何遍历⼀颗⼆叉树

1. 前序遍历（Preorder Traversal） 顺序：根节点 -> 左子树 -> 右子树 递归实现

▼
cpp
复制代码
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

void preorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->val << " ";
    preorderTraversalRecursive(root->left);
    preorderTraversalRecursive(root->right);
}

迭代实现

▼
cpp
复制代码
void preorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::stack<TreeNode*> stack;
    stack.push(root);
    while (!stack.empty()) {
        TreeNode* node = stack.top();
        stack.pop();
        std::cout << node->val << " ";
        if (node->right) {
            stack.push(node->right);
        }
        if (node->left) {
            stack.push(node->left);
        }
    }
}

2. 中序遍历（Inorder Traversal） 顺序：左子树 -> 根节点 -> 右子树 递归实现

▼
cpp
复制代码
void inorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    inorderTraversalRecursive(root->left);
    std::cout << root->val << " ";
    inorderTraversalRecursive(root->right);
}

迭代实现

▼
cpp
复制代码
void inorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    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();
        std::cout << current->val << " ";
        current = current->right;
    }
}

3. 后序遍历（Postorder Traversal） 顺序：左子树 -> 右子树 -> 根节点 递归实现

▼
cpp
复制代码
void postorderTraversalRecursive(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    postorderTraversalRecursive(root->left);
    postorderTraversalRecursive(root->right);
    std::cout << root->val << " ";
}

迭代实现

▼
cpp
复制代码
void postorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::stack<TreeNode*> stack1;
    std::stack<TreeNode*> 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()) {
        std::cout << stack2.top()->val << " ";
        stack2.pop();
    }
}

总结 前序遍历：根节点 -> 左子树 -> 右子树 中序遍历：左子树 -> 根节点 -> 右子树 后序遍历：左子树 -> 右子树 -> 根节点