leetcode:二叉树的左右子树反转的递归和迭代的C++实现

问题描述

给定一个二叉树，将其每个节点的左右子树进行反转。

解决方案

以下是 C++ 代码实现：

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }

    // 交换当前节点的左右子树
    TreeNode* temp = root->left;
    root->left = root->right;
    root->right = temp;

    // 递归反转左右子树
    invertTree(root->left);
    invertTree(root->right);

    return root;
}

代码解释

1. 如果当前节点为空，则直接返回 nullptr。
2. 交换当前节点的左右子树。
3. 递归地对左子树和右子树进行相同的操作。
4. 返回当前节点作为新的根节点。

递归和迭代方法

上述解决方案使用了递归方法，它是简洁且易于理解的。然而，也可以使用迭代方法来反转二叉树，通常使用队列或栈来实现。

以下是使用队列进行迭代的 C++ 代码示例：

TreeNode* invertTreeIterative(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* current = q.front();
        q.pop();
        
        // 交换当前节点的左右子树
        TreeNode* temp = current->left;
        current->left = current->right;
        current->right = temp;
        
        // 将子节点加入队列
        if (current->left != nullptr) {
            q.push(current->left);
        }
        if (current->right != nullptr) {
            q.push(current->right);
        }
    }
    
    return root;
}

在迭代方法中，我们使用一个队列来存储那些需要交换子节点的树节点。在队列不为空的情况下，我们不断地从队列中取出节点，交换它们的左右子节点，然后将它们的子节点（如果存在的话）加入队列中继续处理。这个过程会持续到队列为空，即所有节点都被处理过为止。