当前位置：
  1. 首页
  2. 剑指offer刷题第五期
  3. 问题详情

【二叉树专题】剑指 Offer 27. 二叉树的镜像

本问题对应课程链接：剑指offer刷题第五期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi
155 23

共以下 23 个回答

  • QQiing 普通 2023年9月23日 下午11:28

    class Solution {
    public:
    TreeNode* mirrorTree(TreeNode* root) {
    if(root NULL)
    {
    return NULL;
    }
    TreeNode* left = mirrorTree(root->left);
    TreeNode* right = mirrorTree(root->right);
    root->right = left;
    root->left = right;
    return root;
    }
    };
    时间复杂度：O(n)，空间复杂度：O(n)

    0 赞同 0 条回复
  • 谁仁 普通 2023年9月11日 下午5:00

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

    // 递归实现二叉树镜像
    void mirrorTree(TreeNode* root) {
    if (root NULL) {
    return;
    }
    // 递归处理左子树和右子树，交换左右子树的值
    TreeNode* left = root->left;
    root->left = root->right;
    root->right = left;
    // 递归处理左子树和右子树，交换左右子树的值
    mirrorTree(root->left);
    mirrorTree(root->right);
    }//时间复杂度O（n），空间复杂度O（n）

    0 赞同 0 条回复
  • Di questa storia sempre a lie to 普通 2023年9月4日 下午10:06

    class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
    if not root:
    return root
    TreeNode* left = mirrorTree(root.left)
    TreeNode* right= mirrorTree(root.right)
    root.left = right
    root.right = left
    return root

    时间复杂度：O(N)
    空间复杂度：O(N)

    0 赞同 0 条回复
  • Miracle· 普通 2023年9月3日 下午8:42

    时间复杂度o(n)
    ···
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    * int val;
    * TreeNode left;
    * TreeNode *right;
    * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
    class Solution {
    public:
    TreeNode     mirrorTree(TreeNode* root) {
    if (root nullptr) return nullptr;
    TreeNode *left = mirrorTree(root->left);
    TreeNode *right = mirrorTree(root->right);
    root->left = right;
    root->right = left;
    return root;
    }
    };
    ···

    0 赞同 0 条回复
  • 黎明之前 普通 2023年9月3日 下午3:01

    class Solution{
    public: Treenode *mirrorTree(Treenode *root)
    {
    //当二叉树只有一边的时候没有镜像
    if(root NULL||root->rightNULL&&root->leftNULL)
    return root;
    //递归
    TreeNode *left= mirrorTree(root->left);
    TreeNode *right= mirrorTree(root->right);
    root->left = right;//将右叉树的值给左叉树
    root->right= left;//将左叉树的值给右叉树
    return root;
    }；

    }

    0 赞同 0 条回复
  • Marc 普通 2023年9月2日 下午5:45 
    class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None 
        tmp = root.left 
        root.left = self.mirrorTree(root.right) 
        root.right = self.mirrorTree(tmp)  
        return root

    复杂度O(n)

    0 赞同 0 条回复
  • 羊毛同学 普通 2023年8月31日 下午10:45

    打卡

    /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        //函数作用：输出以root指向的根节点的二叉树的镜像
        //结束条件
        if(root == NULL || root->left == NULL&& root->right == NULL)
           return root; 
        //等价关系式
        TreeNode * left = mirrorTree(root->left);
        TreeNode * right = mirrorTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};
    0 赞同 0 条回复
  • sincere 普通 2023年8月26日 上午12:03
    • 思路：递归翻转子树的镜像，结束条件是当前节点为叶子节点或空，本层处理逻辑是交换子节点
    • 复杂度：时间复杂度O(n)，空间复杂度O(1)
    class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return root;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;

        return root;
    }
}
    0 赞同 0 条回复
  • sc_Yang 普通 2023年8月24日 下午11:00

    时间复杂度O(n)
    空间复杂度O(1)

    /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == NULL){
            return NULL;
        }
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};
    0 赞同 0 条回复
  • 💮黧大王.exe 普通 2023年8月21日 下午11:02

    时间复杂度O(n)
    空间复杂度O(n)
    class Solution {
    public:
    TreeNode* mirrorTree(TreeNode* root) {
    if(rootNULL) return NULL;
    TreeNode* left=mirrorTree(root->left);
    TreeNode* right=mirrorTree(root->right);
    root->left=right;
    root->right=left;
    return root;
    }
    };

    0 赞同 0 条回复
  • Sheng 永久会员 2023年8月21日 下午3:42

    时间复杂度O(n) 空间复杂度O(n)
    ”’java
    //二叉树的镜像
    public TreeNode mirrorTree(TreeNode root) {
    if(root null) return null;

        TreeNode tmp;
    tmp = mirrorTree(root.left);
    root.left = mirrorTree(root.right);
    root.right = tmp;

    return root;
}
    0 赞同 0 条回复
  • 木木 普通 2023年8月21日 下午2:52

    時間複雜度: O(n) 空間複雜度: O(n) 依照遞迴的層數, 這邊n為總節點數量
    遞迴遍歷 左右子樹, 一直到兩邊都到盡頭, 此時對於根節點左右只有各一個節點, 只需要將左右兌換一下即可

    
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
      if (root == nullptr) {
        return root;
      }
      TreeNode* left = mirrorTree(root->left);
      TreeNode* right = mirrorTree(root->right);
      root->left = right;
      root->right = left;
      return root;

    }
};
    0 赞同 0 条回复
  • 辰北、 普通 2023年8月21日 上午10:35

    做俩中间值，leftright暂存，后面继续相反赋值递归到空；

    “`c
    struct TreeNode* mirrorTree(struct TreeNode* root){
    if(rootNULL){
    return NULL;
    }
    struct TreeNode* left= mirrorTree(root->left);
    struct TreeNode* right = mirrorTree(root->right);
    root->left=right;
    root->right=left;
    return root;
    }

    0 赞同 0 条回复
  • 逸兴遄飞 普通 2023年8月21日 上午9:42
    • 时间复杂度：O(N)
    • 空间复杂度：O(N)
    class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        // 递归所有节点的左右子树
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        // 遍历当前节点的左右子树，并将其进行交换
        root.left = right;
        root.right = left;
        return root;
    }
}
    0 赞同 0 条回复
  • 小肸 永久会员 2023年8月20日 下午9:21 
    class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        //先交换后递归
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}
    0 赞同 0 条回复
  • 木子有点甜🍒 普通 2023年8月19日 下午2:19

    #自己写出来的递归加1
    class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
    if not root: return None
    mirror_tree = TreeNode(root.val)
    mirror_tree.left = self.mirrorTree(root.right)
    mirror_tree.right = self.mirrorTree(root.left)

        return mirror_tree
    0 赞同 0 条回复
  • c 普通 2023年8月19日 下午12:59

    递归

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null){
            return root;
        }
        change(root);
        return root;
    }
    public void change(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        change(left);
        change(right);
        root.left=right;
        root.right=left;
    }
}
    0 赞同 0 条回复
  • 别扒拉我 普通 2023年8月18日 下午10:23

    1、递归
    2、层次遍历

    class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}
// 层次遍历
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node = null;
        queue.add(root);
        while(!queue.isEmpty()){
            node = queue.poll();
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }

        return root;
    }
}
    0 赞同 0 条回复
  • 海浪漂哇漂 普通 2023年8月18日 下午10:17

    一开始我是这么写的，结果不对。

    class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        root.left = mirrorTree(root.right);
        root.right =  mirrorTree(root.left);
        return root;
    }
}

    问题出在这两行代码上：

    root.left = mirrorTree(root.right);
root.right =  mirrorTree(root.left);

    当完成第一行的执行后，root.left 的值已经被改变了。因此，在第二行调用 mirrorTree(root.left) 时，实际上是在调用已经被镜像过的右子树，应该首先保存原始的左右子树的引用，然后进行交换。这样可以避免此类问题。下面是修正后的代码：

    class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;
        }
        TreeNode originalLeft = root.left;
        TreeNode originalRight = root.right;

        root.left = mirrorTree(originalRight);
        root.right = mirrorTree(originalLeft);

        return root;
    }
}
    0 赞同 0 条回复
  • 行动派小彩笔 普通 2023年8月18日 下午6:56 
     // 递归思想,前序遍历，每次访问一个节点交换他的左右子树
 // 时间(n),空间链表O(n)
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        TreeNode* tmp = root->right;
        root->right = mirrorTree(root->left);
        root->left = mirrorTree(tmp);
        return root;
    }
};
 // 层次遍历，每次访问一个节点，就交换他的左右子树
 // 时间O(n),空间O(n);
class Solution {
public:
    stack<TreeNode*> stk;
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        stk.push(root);
        while(!stk.empty())
        {
            TreeNode* node = stk.top();
            stk.pop();
            if(node->left) stk.push(node->left);
            if(node->right) stk.push(node->right);
            swap(node->left,node->right);
        }
        return root;
    }
};
    0 赞同 0 条回复
  • mpweixin用户 永久会员 2023年8月18日 下午5:06 
    class Solution {
    //时间复杂度O(n); 空间复杂度O(h)，平均而言O(logn)
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode l = mirrorTree(root.left);
        TreeNode r = mirrorTree(root.right);
        root.right = l;
        root.left = r;
        return root;
    }
}
    0 赞同 0 条回复
  • JustRtn 普通 2023年8月18日 下午4:34

    时间复杂度O(n), 空间复杂度O(n)

    // 递归
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        TreeNode *node = root->left;
        root->left = root->right;
        root->right = node;
        mirrorTree(root->left);
        mirrorTree(root->right);
        return root;
    }
};

// 广度优先
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }

        std::stack<TreeNode *> nodes;
        nodes.push(root);

        while (!nodes.empty()) {
            auto *tmp = nodes.top();
            nodes.pop();
            auto *n = tmp->left;
            tmp->left = tmp->right;
            tmp->right = n;
            if (tmp->left)
                nodes.push(tmp->left);
            if (tmp->right)
                nodes.push(tmp->right);
        }
        return root;
    }
};
    0 赞同 0 条回复
  • 帝心引力 永久会员 2023年8月18日 下午2:25 
    时间o(n), 空间o(n)
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == NULL){
            return NULL;
        }
        TreeNode* lTree = mirrorTree(root->left);
        TreeNode* rTree = mirrorTree(root->right);

        root->left = rTree;
        root->right = lTree;

        return root;
    }
};
    0 赞同 0 条回复

# 回答此问题

后才能回答