二叉树的遍历算法复杂性

二叉树的遍历算法复杂性取决于二叉树的节点数n。对于深度优先遍历，包括先序遍历、中序遍历和后序遍历，时间复杂度为O(n)，空间复杂度为O(h)，其中h为二叉树的高度。对于广度优先遍历，即层次遍历，时间复杂度为O(n)，空间复杂度为O(w)，其中w为二叉树的最大宽度。

// C++版本的二叉树遍历算法示例
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;

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

// 先序遍历
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p || !s.empty()) {
        if (p) {
            res.push_back(p->val);
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
    return res;
}

// 中序遍历
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            res.push_back(p->val);
            p = p->right;
        }
    }
    return res;
}

// 后序遍历
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> s;
    TreeNode* p = root;
    TreeNode* last = NULL;
    while (p || !s.empty()) {
        if (p) {
            s.push(p);
            p = p->left;
        } else {
            TreeNode* top = s.top();
            if (top->right && top->right != last) {
                p = top->right;
            } else {
                res.push_back(top->val);
                last = top;                s.pop();
            }
        }
    }
    return res;
}

// 层次遍历
vector<int> levelOrder(TreeNode* root) {
    vector<int> res;
    queue<TreeNode*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        TreeNode* p = q.front();
        q.pop();
        res.push_back(p->val);
        if (p->left) q.push(p->left);
        if (p->right) q.push(p->right);
    }
    return res;
}