递归实现二叉树左右子树交换

二叉树左右子树交换可以使用非递归的方式实现，可以借助栈来完成。具体实现步骤如下： 1. 声明一个栈，将根节点入栈。 2. 循环遍历栈，直至栈为空。循环中的操作如下： a. 出栈一个节点，将其左右子节点交换。 b. 如果其左子节点不为空，则将左子节点入栈。 c. 如果其右子节点不为空，则将右子节点入栈。 以下是具体的实现过程的 Python 代码示例： ```python def invert_tree(root): if not root: return None stack = [root] while stack: node = stack.pop() node.left, node.right = node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root ``` 以上代码中，`root` 表示二叉树的根节点。函数 `invert_tree` 通过栈的方式遍历二叉树，并将每个节点的左右子树进行交换。最后返回根节点即可。

### 头歌平台非递归实现二叉树左右子树交换 在头歌平台上，可以通过队列或者栈来实现二叉树左右子树的非递归交换。以下是基于广度优先搜索（BFS）的思想，利用队列完成这一功能的具体代码示例。 #### 使用队列实现非递归左右子树交换 通过队列逐层处理节点，并在其过程中交换左右子树的位置： ```cpp #include <iostream> #include <queue> using namespace std; // 定义二叉树节点结构体 struct TreeNode { char data; TreeNode* lchild; TreeNode* rchild; TreeNode(char val) : data(val), lchild(nullptr), rchild(nullptr) {} }; void swapChildren(TreeNode* root) { if (root == nullptr) return; // 如果根节点为空，则无需操作 queue<TreeNode*> q; // 创建队列用于存储待处理的节点 q.push(root); // 将根节点入队 while (!q.empty()) { // 当队列不为空时继续执行 TreeNode* current = q.front(); // 获取当前节点 q.pop(); // 出队 // 交换当前节点的左右子树 TreeNode* temp = current->lchild; current->lchild = current->rchild; current->rchild = temp; // 如果存在左子树，将其加入队列 if (current->lchild != nullptr) { q.push(current->lchild); } // 如果存在右子树，将其加入队列 if (current->rchild != nullptr) { q.push(current->rchild); } } } // 测试函数：创建一棵简单的二叉树并打印其先序遍历结果 int main() { // 构建测试用的二叉树 A / \ B C /\ D E TreeNode* root = new TreeNode('A'); root->lchild = new TreeNode('B'); root->rchild = new TreeNode('C'); root->lchild->lchild = new TreeNode('D'); root->lchild->rchild = new TreeNode('E'); cout << "原始二叉树先序遍历：" << endl; void preOrderTraversal(TreeNode* node); // 声明先序遍历函数 preOrderTraversal(root); // 调用左右子树交换函数 swapChildren(root); cout << "\n交换后的二叉树先序遍历：" << endl; preOrderTraversal(root); return 0; } // 先序遍历辅助函数 void preOrderTraversal(TreeNode* node) { if (node == nullptr) return; cout << node->data << " "; preOrderTraversal(node->lchild); preOrderTraversal(node->rchild); } ``` 上述代码实现了非递归方式下的左右子树交换逻辑[^1]。核心思想是借助队列按层次访问每个节点，在每次访问时直接交换该节点的左右孩子指针。 --- #### 关于时间复杂度和空间复杂度分析 - **时间复杂度**：O(n)，其中 n 是二叉树中节点的数量。因为每个节点都会被访问一次。 - **空间复杂度**：O(w)，w 表示二叉树的最大宽度（即某一层最多含有的节点数），这是由队列的空间需求决定的。 --- ###