数据结构C语言 关于二叉树的基本问题

Question

经典问题，要将二叉树所有的叶子都左右对换，要求用非递归的办法
比如说现在用
void create（Bitree &T）{
。。。
。。。
。。。
T=（Bitree）maollc（sizeof（TNode））；
T->data=x；
create（T->lchild）；
create（T->rchild）；
}
创建了一个二叉树
如何用非递归算法将所有叶子左右对换那？

求思路和大概的算法，拜托不要网上复制黏贴，主要是讲讲你是怎么想的！

Answer 1

// 递归的代码：
void Swap(Bitree *lpNode)
{
    // 将其左子树和右子树交换
    Bitree *lpTemp = lpNode->left;
    lpNode->left = lpNode->right;
    lpNode->right = lpTemp;
    
    // 如果左子树不为空，则递归左子树
    if (lpNode->left)
    {
        Swap(lpNode->left);
    }
    
    // 如果右子树不为空，则递归右子树
    if (lpNode->right)
    {
        Swap(lpNode->right);
    }
}

// 非递归的算法如下：
list<Bitree *> lstNode;

if (lpRoot != NULL)
{
    lstNode.push_back(lpRoot);    // 首先将二叉树的根节点放到队列中
}

while (!lstNode.empty())
{
    // 取出首元素
    Bitree *lpNode = lstNode.front();
    lstNode.pop_front();
    
    // 交换其左右子树
    Bitree *lpTemp = lpNode->left;
    lpNode->left = lpNode->right;
    lpNode->right = lpTemp;
    
    // 如果左子树不为空，则放入队尾
    if (lpNode->left)
    {
        lstNode.push_back(lpNode->left);
    }
    
    // 如果右子树不为空，则放入队尾
    if (lpNode->right)
    {
        lstNode.push_back(lpNode->right);
    }
}

Answer 2

假如只有一个左孩子，右孩子为空，也要交换吗？