c++非递归先序创建二叉树

在 C++ 中，非递归的先序遍历创建二叉树通常通过栈的数据结构来实现。以下是步骤：

1. **节点初始化**: 首先，你需要有一个表示二叉树节点的结构体或类，包含值和指向左右子节点的指针。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

2. **辅助函数**: 创建一个用于将当前节点压入栈并处理左子节点的函数。当遇到空节点或已经遍历完左子树时，从栈顶取出节点作为根节点，并访问其右子节点。

void buildTreeHelper(TreeNode** root, vector<int>& inorder, int start, int end) {
    if (start > end)
        return;

    // 找到当前节点的位置
    int index = searchInorder(inorder, start, end);
    TreeNode* node = new TreeNode(inorder[index]);

    // 先访问左子树
    buildTreeHelper(&node->left, inorder, start, index - 1);

    // 然后将当前节点压入栈
    stack<TreeNode*> s;
    s.push(node);

    // 访问右子树
    buildTreeHelper(&node->right, inorder, index + 1, end);
}

3. **主函数**: 初始化根节点为空，然后提供先序遍历序列（通常是递增的），调用 `buildTreeHelper` 函数创建二叉树。

int main() {
    vector<int> inorder = {1, 2, 4, 5, 3};
    TreeNode* root = nullptr;
    buildTreeHelper(&root, inorder, 0, inorder.size() - 1);
    // ... (其他操作，如打印、遍历等)
    return 0;
}