二叉树后续遍历C++代码

void postorderTraversal(struct TreeNode* root){
if(root == NULL){
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}

相关问题

请给出二叉树后续遍历非递归算法的c++完整代码

当然，以下是二叉树后续遍历的非递归算法的C++完整代码：

#include <stack>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }

        stack<TreeNode*> s;
        TreeNode* last_visited = NULL;
        while (root || !s.empty()) {
            while (root) {
                s.push(root);
                root = root->left;
            }

            root = s.top();
            if (!root->right || root->right == last_visited) {
                res.push_back(root->val);
                s.pop();
                last_visited = root;
                root = NULL; // 这里需要将 root 置空，否则会重复 push 进栈中
            } else {
                root = root->right;
            }
        }
        return res;
    }
};

这里使用了一个栈来模拟递归的过程。首先将根节点入栈，然后将根节点的左子树全部入栈，直到左子树为空。此时，从栈中弹出栈顶元素，如果其右子树为空或已经被访问过，则访问该节点，并将其标记为已访问过，否则将其右子树入栈。重复以上步骤直到栈为空。

二叉树层序遍历算法c++

二叉树的层序遍历（Level Order Traversal）在C++中可以通过递归或迭代的方式实现。这里我们展示一个迭代的版本，因为它更常见且不涉及深度优先搜索[^1]。

#include <iostream>
#include <queue>

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

// 层次遍历函数
void levelOrderTraversal(TreeNode* root) {
    if (root == nullptr) return;

    std::queue<TreeNode*> queue; // 使用队列存储每一层的节点
    queue.push(root);

    while (!queue.empty()) {
        TreeNode* node = queue.front(); // 取当前层的第一个节点
        std::cout << node->val << " "; // 访问该节点
        queue.pop();

        // 将当前节点的左右子节点加入队列，以便后续访问
        if (node->left != nullptr)
            queue.push(node->left);
        if (node->right != nullptr)
            queue.push(node->right);
    }
}

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);

    levelOrderTraversal(root); // 输出：1 2 3 4 5

    return 0;
}