遍历二叉树c++递推

以下是C++中二叉树的三种遍历方式的递归实现和非递归实现：

1. 先序遍历

递归实现：

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

非递归实现：

void preorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
}

2. 中序遍历

递归实现：

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

非递归实现：

void inorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node != nullptr || !s.empty()) {
        while (node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        cout << node->val << " ";
        node = node->right;
    }
}

3. 后序遍历

递归实现：

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

非递归实现：

void postorder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    TreeNode* last = nullptr;
    while (node != nullptr || !s.empty()) {
        while (node != nullptr) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        if (node->right == nullptr || node->right == last) {
            cout << node->val << " ";
            s.pop();
            last = node;
            node = nullptr;
        } else {
            node = node->right;
        }
    }
}
--相关问题--: