用C++编写复制二叉树非递归算法

复制二叉树的非递归算法可以使用栈来实现。具体步骤如下：

1. 新建一个栈，把原二叉树的根节点入栈。
2. 每次从栈中取出一个节点，创建一个新节点并复制原节点的值，将新节点作为复制二叉树的相应节点。
3. 如果原节点的左子节点非空，那么将其入栈；如果右子节点非空，也将其入栈。
4. 重复执行步骤2-3，直到栈为空。

下面是代码实现：

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

TreeNode* cloneTree(TreeNode* root) {
    if (!root) return NULL;
    stack<TreeNode*> s;
    s.push(root);
    TreeNode* newRoot = new TreeNode(root->val);
    TreeNode* curNew = newRoot;
    while (!s.empty()) {
        TreeNode* cur = s.top();
        s.pop();
        if (cur->left) {
            s.push(cur->left);
            curNew->left = new TreeNode(cur->left->val);
            curNew = curNew->left;
        }
        if (cur->right) {
            s.push(cur->right);
            curNew->right = new TreeNode(cur->right->val);
            curNew = curNew->right;
        }
    }
    return newRoot;
}

注意，在栈中除了存储原二叉树的节点，还需要存储相应的新节点，以便在后续的操作中链接新节点。