宁永久会员 2023年3月10日上午10:22

时间复杂度O(N)，空间复杂度树的高度，最差情况下O(N)

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

0 赞同 0 条回复

lucca 普通 2023年1月3日下午3:03

递归，交换，没什么好说的 O（N）

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

0 赞同 0 条回复

PatNick 普通 2022年12月20日下午5:17

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if root == None:
            return
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
       # 左右子树交换位置
        left = root.left
        right = root.right
        root.left = right
        root.right = left

        return root

0 赞同 0 条回复

如梦似歌普通 2022年12月15日下午3:48

class Solution {

    /**
     *方法: 通过递归遍历二叉树，交换每个结点的左/右结点，即可生成二叉树的镜像
     *时间复杂度: T(n) = O(n) 立二叉树镜像需要遍历树的所有节点，占用 O(N)O(N) 时间。
     *空间复杂度: S(n) = O(n) 最差情况下(当二叉树退化为链表时)，递归需要使用O(n)大小的占空间。
     */
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return null;  //当结点为空时，返回null(递归的终止条件)
        }
        //否则对二叉树进行递归遍历
        TreeNode tmp = new TreeNode(); //初始化结点tmp，用于暂存root的左孩子结点
        tmp = root.left;
        root.left = mirrorTree(root.right); //递归右子节点，并将返回值作为root的左孩子结点
        root.right = mirrorTree(tmp); //递归左孩子结点(注意这里左孩子已经被改变了，而原来的左孩子结点保存在tmp中)，并将返回值作为root的右孩子结点
        return root;  //最后返回当前结点root
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:08

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        // 先序遍历
        if(root==nullptr) return nullptr;
        swap(root->left,root->right); //中
        root->left = mirrorTree(root->left);//左
        root->right = mirrorTree(root->right);//右
        return root;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2022年11月18日下午2:05

C++
思路：层序遍历，交换左右节点
/**
* 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 root;
if(root && root->left NULL && root->right NULL) return root;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
TreeNode *now = q.front();
q.pop();
if(now->left && now->right) {
TreeNode *temp = now->left;
now->left = now->right;
now->right = temp;
q.push(now->left);
q.push(now->right);
}else if(now->left && !now->right) {
now->right = now->left;
now->left = NULL;
q.push(now->right);
}else if(!now->left && now->right) {
now->left = now->right;
now->right = NULL;
q.push(now->left);
}
}
return root;
}
};

0 赞同 0 条回复

cute. 普通 2022年11月12日下午8:56

思路: 递归+左右交换节点

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

时间复杂度:O(n)
空间复杂度:O(n) 【n为树的高度】

0 赞同 0 条回复

xye 普通 2022年11月11日下午9:55

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Left, root.Right = mirrorTree(root.Right), mirrorTree(root.Left)
    return root
}

时间O(n) 空间O(n)

0 赞同 0 条回复

symbol 普通 2022年11月7日下午12:43

func mirrorTree(root *TreeNode) *TreeNode {
    Help(root)
    return root
}
func Help(root *TreeNode) {
    if root == nil {
        return 
    }
    root.Left, root.Right = root.Right,root.Left//交换当前节点的值
    //遍历左子树
    if root.Left != nil {
        Help(root.Left)
    }
    //遍历右子树
    if root.Right != nil{
        Help(root.Right)
    }
}

0 赞同 0 条回复

Asphyxia 普通 2022年11月4日下午11:10

递归版简单，来个迭代版的

/**
 * 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) {
        queue<TreeNode*> q;
        TreeNode* cur = root;
        if(cur) q.push(cur);
        while(!q.empty()){
            int s = q.size();
            for(int i=0;i<s;i++){
                cur = q.front();
                q.pop();
                if(cur==NULL){
                    continue;
                }
                q.push(cur->left);
                q.push(cur->right);
                TreeNode* temp = cur->left;
                cur->left = cur->right;
                cur->right = temp;
            }
        }
        return root;
    }
};

0 赞同 0 条回复

星河普通 2022年11月3日下午9:27

DFS
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;
    }
}
时间O(N)空间O(N)

0 赞同 0 条回复

一只骆驼普通 2022年11月2日上午10:21

递归

/**
 * 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 = mirrorTree(root.right);
        root.right=mirrorTree(temp);
        return root;
    }
}

0 赞同 0 条回复

虾仁猪心普通 2022年11月1日下午6:29

思路:
递归三要素：
1. 明确你这个函数想要干什么: 交换左子树和右子树的节点
2. 寻找递归结束条件：递归到叶子节点的左右子节点，因为是叶子节点，所以节点为null时结束递归
3. 找出函数的等价关系式：左右子节点交换并返回父节点

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

cxxz 普通 2022年11月1日下午5:47

镜像交给递归函数，交换左右节点，base是当节点的左右均为空时直接返回。

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

乱世枭雄普通 2022年10月31日下午10:14

思路
根不为空时，左子树旋转，右子树旋转，根左连右子树，根右连左子树
左旋转即为将左结点递归，右边同理

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

        return root;
    }
}

0 赞同 0 条回复

Error 普通 2022年10月31日下午10:13

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

时间复杂度 O(n)

0 赞同 0 条回复

酥合普通 2022年10月31日下午10:00

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

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

0 赞同 0 条回复

Y7n05h 普通 2022年10月31日下午10:00

class Solution {
    void clone(TreeNode *root, TreeNode **nRoot) {
        if (!root) {
            *nRoot = nullptr;
            return;
        }
        auto *tmp = new TreeNode(root->val);
        clone(root->left, &tmp->right);
        clone(root->right, &tmp->left);
        *nRoot = tmp;
    }

public:
    TreeNode *mirrorTree(TreeNode *root) {
        TreeNode *newTree;
        clone(root, &newTree);
        return newTree;
    }
};

时间复杂度：O(n)
空间复杂度：O(n) （递归栈）

0 赞同 0 条回复

马啸天永久会员 2022年10月31日下午2:54

public class Solution {

    public TreeNode mirrorTree(TreeNode root) {
        //1.寻找递归结束的条件
        if (root == null || root.left == null && root.right == null) {
            return root;
        }
        //2.让左边右边调换顺序
        TreeNode left = mirrorTree(root.right);
        TreeNode right = mirrorTree(root.left);

        root.left=left;
        root.right=right;

        return root;
    }
}

0 赞同 0 条回复

刺猬普通 2022年10月31日下午1:49

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

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

0 赞同 0 条回复

云雾里普通 2022年10月31日上午7:27

class Solution {
    //BFS后序
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null)return null;
        TreeNode treeNode = new TreeNode(root.val);
        treeNode.left=mirrorTree(root.right);
        treeNode.right=mirrorTree(root.left);
        return treeNode;
    }
    /*public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }*/
}

0 赞同 0 条回复

绍熙普通 2022年10月31日上午6:54

解题思路：
递归解析：
终止条件：当节点 rootroot 为空时（即越过叶节点），则返回 nullnull ；
递推工作：
初始化节点 tmptmp ，用于暂存 rootroot 的左子节点；
开启递归右子节点 mirrorTree(root.right)mirrorTree(root.right) ，并将返回值作为 rootroot 的左子节点。
开启递归左子节点 mirrorTree(tmp)mirrorTree(tmp) ，并将返回值作为 rootroot 的右子节点。
返回值：返回当前节点 rootroot ；

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

小肸永久会员 2022年10月30日下午4:44

思路就是用递归解决，只不过实现方式不同。
方式一：后序遍历的节点访问顺序，递归地得到已经处理好的左、右子树的根节点并交换处理。时间复杂度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;
    }
}

方式二：不用得到已经镜像后的左右子树的节点，而是在遍历节点的同时，交换遍历节点的左右子节点。时间复杂度O(N)，空间复杂度还是取决于树的高度。
前序遍历

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        mirrorTreeCore(root);
        return root;
    }
    private void mirrorTreeCore(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        mirrorTree(root.left); //左
        mirrorTree(root.right); //右

    }
}

后序遍历

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        mirrorTreeCore(root);
        return root;
    }
    private void mirrorTreeCore(TreeNode root) {
        if (root == null) {
            return;
        }
        mirrorTree(root.left); //左
        mirrorTree(root.right); //右
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

中序遍历(有些特殊，因为中的时候已经交换了左右节点，所以后面还要对root.left处理，而不是root.right，刚开始时我是处理的root.right，可以画图或调试找出错误)

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

0 赞同 0 条回复

Whatever 永久会员 2022年10月30日下午4:43

遍历，然后交换左右子节点，时间O(n)，空间O(n)

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

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

        traverse(root.left);
        traverse(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

}

0 赞同 0 条回复

Chin 普通 2022年10月30日下午3:03

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
      if(root == null) return null;
      //  使用一个新node来记录反转后的值
      TreeNode node = new TreeNode(root.val);
      node.right =   mirrorTree(root.left);
      node.left = mirrorTree(root.right);
      return node;
    }
}

时间复杂度On
空间复杂度On

0 赞同 0 条回复

cxc 普通 2022年10月30日下午2:44

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

        //交换左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

0 赞同 0 条回复

感到自己好渺小普通 2022年10月30日上午11:24

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        //递归三部曲
        //1.明确递归函数的功能mirrorTree()：使根结点为root的二叉树变成镜像
        //2.递归终止条件:当root为null时，退出递归
        //3.构建函数等价关系式，目的是减少问题的规模，直到问题能用递归终止条件解决
        if(root==null)  //当前节点为空时,即越过了叶子节点，返回null
        {
            return null;
        }
        TreeNode right = mirrorTree(root.right);  //进行完镜像的右子树
        TreeNode left = mirrorTree(root.left);  //进行完镜像的左子树
        root.left = right;  //在根节点交换左右子树的位置
        root.right = left;
        return root;
    }
}

0 赞同 0 条回复

天然普通 2022年10月30日上午10:46

学习新思想，做好每一题
辅助栈思想，前面的求深度也是类似的思想，迭代遍历时间复杂度O(0),空间复杂度O(n)

class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return root
        num = [root]
        while num:
            tem = num.pop(0)
            if tem.left:num.append(tem.left)
            if tem.right:num.append(tem.right)
            tem.left,tem.right = tem.right,tem.left
        return root
递归还是不好想呀，练的太少了，慢慢来比较快
class Solution:
    def mirrorTree(self, root: TreeNode) -> TreeNode:
        if not root: return 
        root.left ,root.right = root.right,root.left
        self.mirrorTree(root.left)
        self.mirrorTree(root.right)
        return root

0 赞同 0 条回复

@ 普通 2022年10月30日上午10:21

一.剑指 Offer 27. 二叉树的镜像

思路:递归该二叉树，然后在返回的时候把他的左右子数进行交换即可
时间复杂度: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 条回复

wxc 普通 2022年10月30日上午9:37

额

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

0 赞同 0 条回复

yanshuojune 普通 2022年10月29日下午11:57

解题思路：使用深度优先方法递归遍历二叉树，交换每个节点的左右子节点，直到子节点为None。
时间复杂度：O(n)
空间复杂度：O(n)

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

        return root

0 赞同 0 条回复

lobort 普通 2022年10月29日下午10:26

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.right = left;
        root.left = right;
        return root;
    }
}

时间空间 O(n)

0 赞同 0 条回复

猫猫真可爱普通 2022年10月29日下午8:50

迭代，用一个结点来保存，防止丢失。

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

0 赞同 0 条回复

波波_1936 普通 2022年10月29日下午7:40

public TreeNode mirrorTree(TreeNode root) {
        //时间复杂度O(n) 遍历所有节点
        //空间复杂度O(n)//调用栈是整个树的所有节点
        if (root == null) return root;
        TreeNode right = root.right;
        root.right = root.left;
        root.left = right;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;

    }

0 赞同 0 条回复

T 普通 2022年10月29日下午6:43

左右子树交换

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

0 赞同 0 条回复

派大星普通 2022年10月29日下午6:33

class Solution {
//时间复杂度O(n)
//空间复杂度O(n)
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null)){
            return root;
        }
        TreeNode l = root.left;
        root.left = root.right;
        root.right = l;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;

    }
}

0 赞同 0 条回复

阿白普通 2022年10月29日下午5:50

后序遍历，对每一个子树进行镜像
时间O（n），空间O（n）

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

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

        root->left = r;
        root->right = l;
        return root;
    }
};

0 赞同 0 条回复

你有点可爱喔普通 2022年10月29日下午5:19

class Solution {
    //时间复杂度O(n), 时间复杂度O(n)
    public TreeNode mirrorTree(TreeNode root) {
        //递归
        if(root == null || (root.right==null&&root.left ==null)){
                return root;
        }
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);

        root.left = right;
        root.right = left;
        return root;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月29日下午5:03

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

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

0 赞同 0 条回复

Tolkien 永久会员 2022年10月29日下午3:56

/**
     * 递归
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public TreeNode mirrorTree(TreeNode root) {
        // 1. 递归结束条件
        if (root == null) {
            return null;
        }

        // 2. 等价关系式
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;

        return root;
    }

0 赞同 0 条回复

just 普通 2022年10月29日下午3:46

//recursion递归
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(!root) return nullptr;
mirrorTree(root->left);
mirrorTree(root->right);
swap(root->left,root->right);
return root;

};

0 赞同 0 条回复

Haoyun 普通 2022年10月29日下午1:15

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

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

0 赞同 0 条回复

Gg 普通 2022年10月29日下午12:55

 // 利用队列进行遍历
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 镜像每一个子树，最后得到的就是整棵树的镜像
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;

    }
}
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null){
            return root;
        }
        Deque<TreeNode> dq = new ArrayDeque<>();
        dq.offer(root);
        while(!dq.isEmpty()){
            TreeNode curr = dq.poll();
            // 交换
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;
            // 放入子树节点 等待交换
            if(curr.left != null){
                dq.offer(curr.left);
            }
            if(curr.right != null){
                dq.offer(curr.right);
            }
        }
        return root;
    }
}

0 赞同 0 条回复

是梦终空永久会员 2022年10月29日上午11:39

递归交换叶子结点
时间O(n)
空间O(n)

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

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

        root.right = t1;
        root.left = t2;
        return root;
    }
}

0 赞同 0 条回复

庄重普通 2022年10月29日上午11:14

//  思路：
//     1.函数功能：交换左右子树
//     2.关系式：root->left = rNode;
//               root->right = lNode;
//     3.初始值 root == NULL  --> return root;
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == NULL) return root;

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

        return root;    
    }
};
//时间复杂度O(logn)
//空间复杂度O(1)

0 赞同 0 条回复

鸿渐普通 2022年10月29日上午11:00

递归真的是太抽象了

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

0 赞同 0 条回复

追普通 2022年10月29日上午10:11

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

        return root;
    }
};

递归的返回条件还是有点迷糊，需要再仔细多看看递归

0 赞同 0 条回复

浅夏的无奈普通 2022年10月29日上午12:12

//时间复杂度：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 条回复

狗蛋儿普通 2022年10月28日下午10:23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    //镜像本质也是遍历，因此我们还是要首先选择遍历方式
    //这里我们只是需要在中操作的时候交换两者即可
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot == nullptr) return pRoot;
        swap(pRoot->left,pRoot->right);
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
    }
};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月28日下午9:51

时间复杂度O(N)会遍历每一个节点空间复杂度O(N) 一般情况下遍历深度为logn，最坏情况下为链表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.right = left;
        root.left = right;//反转当前节点
        return root;
    }
}

栈迭代

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            TreeNode tmp = cur.left;
            cur.left = cur.right;
            cur.right = tmp;
            if(cur.left != null) stack.push(cur.left);
            if(cur.right != null) stack.push(cur.right);
        }
        return root;
    }
}

队列迭代

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
       Queue<TreeNode> queue = new LinkedList<>();
       queue.offer(root);
       while(!queue.isEmpty()){
           TreeNode cur = queue.poll();
           TreeNode tmp = cur.left;
           cur.left = cur.right;
           cur.right = tmp;
           if(cur.left != null) queue.offer(cur.left);
           if(cur.right != null) queue.offer(cur.right);
       }
       return root;
    }
}

0 赞同 0 条回复

青木普通 2022年10月28日下午9:20

 /**
    函数的功能是返回翻转后的树；
    将节点的左右进行转换；
    对左子树进行转换；
    对右子树进行转换；
    返回节点

    时间复杂度O(n)
    空间复杂度O(Height)
  */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root==null) return root;

        TreeNode node = root.left;
        root.left = root.right;
        root.right = node;

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

        return root;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月28日下午9:14

1、判断特殊情况，当根节点为空或者根节点的左右节点为空时，直接返回根节点
2、无特殊情况，则采用递归，分别镜像根节点的左右节点
3、根的左右指针进行重新指向

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->right = left;
        root->left = right;
        return root;

    }
};

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月28日下午9:07

时间复杂度为O（n），空间复杂度为O（lgn）

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

黎昕普通 2022年10月28日下午8:47

递归，和深搜的操作没有区别
时间 O(n)
空间 O(1)

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

0 赞同 0 条回复

So 普通 2022年10月28日下午8:29

/**
 * 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 || (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 条回复

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

共以下 55 个回答

递归，交换，没什么好说的 O（N）

一.剑指 Offer 27. 二叉树的镜像

# 回答此问题取消回复

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

共以下 55 个回答

递归，交换，没什么好说的 O（N）

一.剑指 Offer 27. 二叉树的镜像

# 回答此问题 取消回复

# 回答此问题取消回复