输入二叉树，非递归算法实现先序遍历中序遍历后续遍历的完整代码和算法分析

好的，下面是用C++实现的完整程序代码和算法分析：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

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

// 创建二叉树
TreeNode* createTree(vector<int>& nums, int index) {
    if (index >= nums.size() || nums[index] == -1) {
        return NULL;
    }
    TreeNode* root = new TreeNode(nums[index]);
    root->left = createTree(nums, index * 2 + 1);
    root->right = createTree(nums, index * 2 + 2);
    return root;
}

// 非递归实现先序遍历
void preorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right != NULL) {
            s.push(node->right);
        }
        if (node->left != NULL) {
            s.push(node->left);
        }
    }
}

// 非递归实现中序遍历
void inorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s;
    TreeNode* node = root;
    while (node != NULL || !s.empty()) {
        if (node != NULL) {
            s.push(node);
            node = node->left;
        } else {
            node = s.top();
            s.pop();
            cout << node->val << " ";
            node = node->right;
        }
    }
}

// 非递归实现后序遍历
void postorder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    stack<TreeNode*> s1, s2;
    s1.push(root);
    while (!s1.empty()) {
        TreeNode* node = s1.top();
        s1.pop();
        s2.push(node);
        if (node->left != NULL) {
            s1.push(node->left);
        }
        if (node->right != NULL) {
            s1.push(node->right);
        }
    }
    while (!s2.empty()) {
        TreeNode* node = s2.top();
        s2.pop();
        cout << node->val << " ";
    }
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, -1, 6, -1, -1, 7};
    TreeNode* root = createTree(nums, 0);
    cout << "先序遍历：";
    preorder(root);
    cout << endl;
    cout << "中序遍历：";
    inorder(root);
    cout << endl;
    cout << "后序遍历：";
    postorder(root);
    cout << endl;
    return 0;
}

算法分析：

- 创建二叉树：使用递归实现，时间复杂度为O(n)，空间复杂度为O(n)。
- 非递归实现先序遍历：使用栈实现，每个节点最多被访问两次，时间复杂度为O(n)，空间复杂度为O(n)。
- 非递归实现中序遍历：使用栈实现，每个节点最多被访问两次，时间复杂度为O(n)，空间复杂度为O(n)。
- 非递归实现后序遍历：使用两个栈实现，每个节点最多被访问两次，时间复杂度为O(n)，空间复杂度为O(n)。

综上所述，以上三种非递归算法时间复杂度和空间复杂度相同，为O(n)和O(n)。