【二叉树专题】剑指 Offer 27. 二叉树的镜像-跟着帅地玩副业，开拓第二曲线PlayOffer

大大普通 2023年11月14日上午9:13

c++
 //递归解法
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
     if(root<span class="text-highlighted-inline" style="background-color: #fffd38;">NULL)return NULL;
     TreeNode* h=root->left;
     root->left=mirrorTree(root->right);
     root->right=mirrorTree(h);
    return root;
    }
};</span>

//非递归解法 利用栈或者队列都可以
//因为上已成的左右节点已经交换了，下一层可以先交换左，也可以先交换右

class Solution {
public:
     stack<TreeNode<em>>s;
    TreeNode</em> mirrorTree(TreeNode* root) {
     if(root<span class="text-highlighted-inline" style="background-color: #fffd38;">NULL)return NULL;
     s.push(root);
     while(!s.empty()){
         TreeNode* t=s.top();
         s.pop();
         if(t->left)s.push(t->left);
         if(t->right)s.push(t->right);
         TreeNode* tmp=t->left;
         t->left=t->right;
         t->right=tmp;
     }
     return root;
    }

0 赞同 0 条回复

九号球普通 2023年11月12日下午7:22

“`java
从上到下依次翻转即可
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if (root == null) {
return null;
}
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode 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月25日下午5:01

/**
* 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 null;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.right = left;
root.left = right;
return root;
}
}
递归

0 赞同 0 条回复

淡色花樱普通 2023年7月18日下午2:43

“`java
时间复杂度O(n) 空间复杂度0(n)
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 条回复

cute. 普通 2023年7月12日下午1:08

思路：递归，交换左右子树

var mirrorTree = function(root) {
    if(root === null || (root.left === null && root.right === null))
        return root;
    let left = mirrorTree(root.left);
    let right = mirrorTree(root.right);
    root.left = right;
    root.right = left;
    return root;
};

0 赞同 0 条回复

jhfuture 普通 2023年7月10日上午10:50

java实现

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;
    }
}

时间复杂度:O(n)，空间复杂度 :O(n)
思路：先确定每个部分的功能，然后对递归范围进行缩减，三对最后的最小单位进行分析

0 赞同 0 条回复

BOZ 普通 2023年7月6日下午11:26

【思路】递归对每棵子树做左右子树的swap
【复杂度】时间复杂度O(n)，空间复杂度O(1)

#include <algorithm>
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if (root == NULL) return root;
        root->left = mirrorTree(root->left);
        root->right = mirrorTree(root->right);
        std::swap(root->left, root->right);
        return root;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年7月6日下午1:51

C++实现

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


        mirrorTree(root -> left);
        mirrorTree(root -> right);

        TreeNode* tmp = nullptr;
        tmp = root -> left;
        root -> left = root -> right;
        root -> right = tmp;
        return root;

    }
};

0 赞同 0 条回复

Sexypig. 普通 2023年7月5日下午2:14

这段代码是一个二叉树的镜像反转函数。给定一个二叉树的根节点，函数会将该二叉树进行镜像反转，并返回反转后的二叉树的根节点。
代码的步骤如下：
1. 首先定义了一个TreeNode类，用于表示二叉树的节点。节点包含一个值val，以及左右子节点left和right。
2. 然后定义了一个Solution类，其中包含了一个mirrorTree函数，用于实现二叉树的镜像反转。
3. 在mirrorTree函数中，首先判断根节点是否为空。如果为空，则直接返回空节点。
4. 如果根节点不为空，接下来进行镜像反转。通过递归调用mirrorTree函数，分别对根节点的左子节点和右子节点进行镜像反转。
5. 反转的方式是通过交换根节点的左右子节点，即将根节点的左子节点赋值为右子节点，右子节点赋值为左子节点。
6. 最后返回反转后的根节点。
这段代码实现了一个二叉树的镜像反转功能，通过递归的方式对二叉树的每个节点进行处理，将其左右子节点进行交换，从而实现整个二叉树的镜像反转。

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

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

0 赞同 0 条回复

断舍离永久会员 2023年7月5日上午7:22

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //空树，直接返回null
        if (root == null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        //根节点入栈
        stack.push(root);
        //当栈内还有元素，说明未遍历完整棵树
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            //叶子节点无左右孩子，不用入栈
            if(node != null){
                stack.push(node.left);
                stack.push(node.right);
                //交换左右孩子
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
        }
        return root;
    }
}

0 赞同 0 条回复

小金子普通 2023年7月5日上午12:16

/** 时间复杂度O(n) 空间复杂度O(n)
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left TreeNode
* Right *TreeNode
* }
*/
func mirrorTree(root *TreeNode) *TreeNode {
if rootnil{
return nil
}
swap(root)
return root
}
func swap(root *TreeNode) (TreeNode,*TreeNode) {
if root.Left!=nil||root.Right!=nil{
root.Left,root.Right=root.Right,root.Left
}
if root.Left!=nil{
swap(root.Left)
}
if root.Right!=nil{
swap(root.Right)
}
return root.Left,root.Right
}

0 赞同 0 条回复

CV大神普通 2023年7月4日下午9:22

public class Offer27 {

    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        //直接换位
        TreeNode left = mirrorTree(root.left);
        root.left = mirrorTree(root.right);
        root.right = left;
        return root;

    }
}

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

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午12:50

递归

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

0 赞同 0 条回复

　　　　　　　　普通 2023年7月3日下午3:53

class Solution {
public:
    bool is(TreeNode* p,TreeNode* q){
        if(!q&&!p)return true;
        if(!q||!p||p->val!=q->val)return false;
        return is(p->left,q->right)&&is(q->left,p->right);
    }
    bool isSymmetric(TreeNode* root) {
        return is(root,root);
    }
};

【时间O(n),空间O(1)】
递归

0 赞同 0 条回复

局外人普通 2023年7月3日上午10:17

思路：前序遍历，将每个左右子树进行交换，即可实现镜像翻转
时间复杂度O(n) 空间复杂度O(n)

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null)  return null;

        TreeNode temp=null;
        temp=root.left;
        root.left=root.right;
        root.right=temp;

        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月3日上午9:53

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

时间和空间复杂度都是O(N)

0 赞同 0 条回复

花老爷普通 2023年6月30日上午8:51

dfs
时间：O(n)
空间：O(n)

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        mirror(root);
        return root;
    }

    private void mirror(TreeNode node) {
        if (node == null) {
            return;
        }
        TreeNode l = node.left;
        node.left = node.right;
        node.right = l;
        mirror(node.left);
        mirror(node.right);
    }
}

bfs
时间：O(n)
空间：O(n)

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        Deque queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) 
                queue.offer(node.left);
            if (node.right != null)
                queue.offer(node.right);
            TreeNode left = node.left;
            node.left = node.right;
            node.right = left;
        }
        return root;
    }
}

0 赞同 0 条回复

地平线真勇敢普通 2023年6月29日下午9:05

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;
}

时间复杂度：o(n),其中n为二叉树节点的数目，会遍历二叉树的每个节点。
空间复杂度：o(n),使用的空间有递归栈的深度

0 赞同 0 条回复

～普通 2023年6月29日上午9:32

方法一：递归
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
traverse(root);
return root;
}
void traverse(TreeNode* root){
if(rootnullptr){
return;
}
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
traverse(root->left);
traverse(root->right);
}
};
方法二：分解问题
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(rootnullptr){
return nullptr;
}
TreeNode* lefttree = mirrorTree(root->left);
TreeNode* righttree = mirrorTree(root->right);
root->right = lefttree;
root->left = righttree;
return root;
}
};
时间复杂度O(n)，空间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月29日上午6:16

时间复杂度O(n)
空间复杂度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) {
        return reverse(root);
    }
    TreeNode* reverse(TreeNode* node) {
        if (!node) {
            return NULL;
        }
        TreeNode* left = reverse(node->left);
        TreeNode* right = reverse(node->right);
        TreeNode* tmp = left;
        node->left = right;
        node->right = tmp;
        return node;
    }
};

0 赞同 0 条回复

Bello~ 普通 2023年6月28日下午10:59

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

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

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月28日下午5:35

时间复杂度：O(n)
空间复杂度：树的高度。

struct TreeNode* mirrorTree(struct TreeNode* root) {
    if (root == NULL || root->left == NULL || root->right ==NULL){
        return root;
    }
    struct TreeNode* left = mirrorTree(root->left);
    struct TreeNode* right = mirrorTree(root->right);
    root->left = right;
    root->right = left;
    return root;
}

0 赞同 0 条回复

江畅普通 2023年6月27日下午11:46

//二叉树的镜像
// 时间复杂度 O(N) 遍历二叉树中的每一个节点
// 空间复杂度 O(N) 递归栈的深度. 平均 O(logN)；在最坏情况下，树形成链状，空间复杂度为 O(N)
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年6月27日下午10:24

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

class Solution {
    // 1. 明确函数功能：输入和返回
    public TreeNode mirrorTree(TreeNode root) {
        // 2. 寻找递归结束条件
        if(root == null) return null;
        // 3. 找出函数等价关系式
        TreeNode right = mirrorTree(root.left);
        TreeNode left = mirrorTree(root.right);
        root.right = right;
        root.left = left;
        return root;
    }
}

0 赞同 0 条回复

小吕普通 2023年6月27日下午8:23

c++实现递归
TreeNode* mirrorTree(TreeNode* root) {
if(rootNULL)return root;
stack<TreeNode> st;
st.push(root);
while(!st.empty())
{
TreeNode temp = st.top();
st.pop();
swap(temp->left,temp->right);
if(temp->left!=NULL)st.push(temp->left);
if(temp->right!=NULL)st.push(temp->right);
}
return root;
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月26日下午9:56

思路：将节点的左右子树的交换，然后再将下一层子树的左右子树进行交换

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

0 赞同 0 条回复

彦，，# 普通 2023年6月26日下午5:08

啊啊啊递归好像有点懂了。
时间复杂度O(n) 空间复杂度O(n)

 TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;
        if(!root->left && !root->right) return root;
        TreeNode* tree_left = mirrorTree(root->left);
        TreeNode* tree_right = mirrorTree(root->right);
        root->left = tree_right;
        root->right = tree_left;
        return root;
    }

0 赞同 0 条回复

屠龙手段普通 2023年6月26日下午4:27

递归 时间复杂度O(n) 空间复杂度O(n)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

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

0 赞同 0 条回复

普通 2023年6月26日下午4:26

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        foreachTrre(root);
        return root;
    }

    public void foreachTrre(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode left = root.left;
        root.left = root.right;
        root.right = left;

        foreachTrre(root.left);
        foreachTrre(root.right);
        return;
    }
}

dfs,时间复杂度O(n)

0 赞同 0 条回复

mpweixin用户普通 2023年6月26日下午3:10

struct TreeNode* mirrorTree(struct TreeNode* root){
 if(root==NULL)
 {
     return root;
 }
  struct TreeNode*t=root->right;
  root->right=root->left;
  root->left=t;
  mirrorTree(root->right);
  mirrorTree(root->left);
  return root;
}

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

0 赞同 0 条回复

残月冷骄阳普通 2023年6月26日上午11:30

复杂度

时间复杂度: $O(n)$
空间复杂度: $O(n)$

Code

/**
 * 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 null;
        }

        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月26日上午12:13

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:

        if not root:
            return root
        # 记下左树反转结果
        leftNode = self.invertTree(root.left)
        root.left = self.invertTree(root.right)
        root.right = leftNode

        return root

0 赞同 0 条回复

大鑫啊普通 2023年6月25日下午11:07

时空复杂度：O(n)
1、还是递归三部曲
2、写出方法参数和返回值
3、写出结束条件
4、找出等价关系

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 条回复

Jerry 普通 2023年6月25日下午10:26

 //递归
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        traverse(root);
        return root;
    }

    public void traverse(TreeNode root) {
        if (root == null) return;

        // 交互 left 和 right 节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        //递归去操作 left right节点
        traverse(root.left);
        traverse(root.right);
    }
}

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

0 赞同 0 条回复

行动派小彩笔普通 2023年6月25日下午10:24

 //递归实现，时间复杂度O(n),空间复杂度(n)，最坏情况，树变成链表
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root||(!root->left&&!root->right)) return root;
        TreeNode* tmp = root->left;
        root->left = mirrorTree(root->right); //这个时候root->left的地址已经改变了，所以需要提前存储left的地址
        root->right = mirrorTree(tmp);

        return root;
    }
};
// 栈实现
//辅助栈，时间复杂度O(n),空间复杂度(n)，
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root||(!root->left&&!root->right)) return root;
        stack<TreeNode*> sk;
        sk.push(root);
        while(!sk.empty())
        {
            TreeNode* node = sk.top();
            sk.pop();
            if(node->left) sk.push(node->left);
            if(node->right) sk.push(node->right);
            swap(node->left,node->right);
        }

        return root;
    }
};

0 赞同 0 条回复

硬核洋葱普通 2023年6月25日下午9:11

/**
 * 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)   return NULL;
        mirrorTree(root->left);
        mirrorTree(root->right);
        swap(root->left, root->right);
        return root;
    }
};

自底向上（左右根）方式递归，交换左节点和右节点，递归终点是空节点
时间复杂度O(n) 空间复杂度 O(h)

0 赞同 0 条回复

désire. 普通 2023年6月25日下午9:10

时间O(1) 空间O(N)
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root NULL) return root;
swap(root->left,root->right);
mirrorTree(root->left);
mirrorTree(root->right);
return root;
}
};

0 赞同 0 条回复

伏月三十普通 2023年6月25日下午8:32

时间复杂度O(n) 空间复杂度树的高度

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

        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;

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

        return root;
    }
}

0 赞同 0 条回复

peach 普通 2023年6月25日下午8:20

思路

递归处理即可，注意要保存一下某个节点

代码

 //递归解法 时间复杂度O(n) 空间复杂度O(logn)
class Solution {
    public TreeNode mirrorTree(TreeNode root) { //这个函数的目的是输出二叉树的镜像
        if(root == null) return null; //终止条件
        TreeNode temp = root.left; //保存左子节点
        root.left = mirrorTree(root.right); //右的镜像被放在左子节点位置
        root.right = mirrorTree(temp); //左的镜像放在右子节点位置
        return root; //返回根节点即可
    }
}

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 条回复

Dsjh 普通 2023年6月25日下午8:16

// c++ 实现
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root){
            return nullptr;
        }
        TreeNode* l = mirrorTree(root->left);
        TreeNode* r = mirrorTree(root->right);


<pre><code>    root->left = r;
    root->right = l;
    return root;
}
</code></pre>

};

0 赞同 0 条回复

怀瑾永久会员 2023年6月25日下午8:14

时间复杂度：O（n）
空间复杂度：O（n）

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 条回复

mpweixin用户永久会员 2023年6月25日下午7:43

//时间O(n)，空间O(logn)
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 条回复

张开怀普通 2023年6月25日下午4:18

/**
 * 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 || (!root->left && !root->right)){
                  return root;
            }

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

            root->left = left;
            root->right = right;

            return root;
      }
}

时间复杂度：O(n)
空间复杂度：树的高度

0 赞同 0 条回复

Ming 普通 2023年6月25日下午3:17

复杂度O(n) O(n)

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 条回复

yxy 普通 2023年6月25日下午2:54

复杂度O(n) 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) return nullptr;
        mirrorTree(root->left);
        mirrorTree(root->right);
        auto tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};

0 赞同 0 条回复

Yodl. 普通 2023年6月25日下午2:23

/**
 * 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;
        }
        root->left=mirrorTree(root->left);
        root->right=mirrorTree(root->right);
        TreeNode* tmp;
        tmp=root->left;
        root->left=root->right;
        root->right=tmp;
        return root;
    }
};
时间复杂度：O(n)
空间复杂度：O(nlogn)

0 赞同 0 条回复

雨落圆荷普通 2023年6月25日下午1:56

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;
}

}
时间复杂度：O(n)
空间：树的高度。

0 赞同 0 条回复

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

共以下 47 个回答

复杂度

Code

思路

代码

# 回答此问题取消回复

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

共以下 47 个回答

复杂度

Code

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复