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

桎梏普通 2023年8月11日下午9:21

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

    // 交换左右子树
    public void swap(TreeNode root) {
        TreeNode tmp = null;
        tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

0 赞同 0 条回复

hi 普通 2023年8月5日下午11:07

注意递归和子树节点反转的顺序

/**
 * 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 || (root -> left == NULL &&  root -> right == NULL)) return root;
        mirrorTree(root -> left);
        mirrorTree(root -> right);
        TreeNode* rn = root -> right;
        root -> right = root -> left;
        root -> left = rn;
        return root;
    }
};

0 赞同 0 条回复

今天没时间刷题普通 2023年7月31日下午10:10

时间On,空间On
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return root;

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

0 赞同 0 条回复

wowo 普通 2023年7月27日上午6:08

时间复杂度O（N）
空间复杂度 O(logN) 最差链式结构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 root

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

        return root

0 赞同 0 条回复

Terence💧 普通 2023年7月18日下午10:04

二叉树镜像

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return root
    }    
    left := mirrorTree(root.Left)
    right := mirrorTree(root.Right)
    root.Right = left
    root.Left = right
    return root
}

0 赞同 0 条回复

doordie. 普通 2023年7月18日下午3:19

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
             if (root == null){
            return null;
        }
        Stack<TreeNode> stack = new Stack();
        // 存储根节点
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
           if(node.left != null) stack.add(node.left);
            if(node.right != null) stack.add(node.right);
            TreeNode temp = node.left;
            node.left = node.right;
            node.right = temp;
        }
        return root;
    }
}

递归

0 赞同 0 条回复

朱志刚普通 2023年7月18日上午8:27

class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==NULL)return root;
        dfs(root);
        return root;
    }
    TreeNode* dfs(TreeNode* root)
    {
        if(root==NULL)return root;

        dfs(root->left);
        dfs(root->right);
        if(root->left==NULL)
        {
            root->left=root->right;
            root->right=NULL;
            return root;
        }
        if(root->right==NULL)
        {
            root->right=root->left;
            root->left=NULL;
            return root;
        }
        TreeNode* temp=root->left;
        root->left=root->right;
        root->right=temp;

        return root;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

0 赞同 0 条回复

Mby 普通 2023年7月17日下午1:42

递归
/**
 * 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;

    }
}

0 赞同 0 条回复

枫梓。普通 2023年7月17日下午1:16

class Solution {
private:
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(!root) return NULL;
        TreeNode *lt = mirrorTree(root->left);
        TreeNode *rt = mirrorTree(root->right);
        root->left = rt;
        root->right = lt;
        return root;
    }
};

递归时间O(n),因为遍历了所有结点。空间O(n),最坏情况是链子状

0 赞同 0 条回复

小季同学普通 2023年7月17日上午8:59

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function mirrorTree(root: TreeNode | null): TreeNode | null {
    // 递归递出条件
    if(!root || (root.left === null && root.right === null))  {
        return root
    }
    const left = mirrorTree(root.left)
    const right = mirrorTree(root.right)
    root.right = left
    root.left = right
    return root

};

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月16日下午10:26

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        // 递归将左右都交换
        if(root==null) return root;
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
    }
}

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

0 赞同 0 条回复

片言莫语普通 2023年7月16日下午9:44

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

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月16日下午9:20

代码如下

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

神经蛙普通 2023年7月16日下午2:26

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

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

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

        return root;
    }
}

0 赞同 0 条回复

Marshan 普通 2023年7月16日上午10:11

递归

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

        return root;
    }
};

0 赞同 0 条回复

ppopp 普通 2023年7月16日上午1:03

/**中文
* 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 root;
mirrorTree(root -> left);
mirrorTree(root -> right);
TreeNode* cur = new TreeNode(-1);
cur = root -> left;
root -> left = root -> right;
root -> right = cur;
return root;
}
};

0 赞同 0 条回复

周小二普通 2023年7月15日下午11:55

 //自顶向下递归
class Solution {
    public TreeNode mirrorTree(TreeNode root) {

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

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月15日下午6:20

Day7：下面是代码

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月15日下午6:10

递归

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function mirrorTree(root: TreeNode | null): TreeNode | null {
    const dfs = (node:TreeNode | null) => {
        if(!node) return;
        dfs(node.left);
        dfs(node.right);
        [node.left,node.right] = [node.right,node.left];
    }
    dfs(root);
    return root;
};

0 赞同 0 条回复

北辰普通 2023年7月15日下午4:55

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

思路：先将要镜像的子树根节点的左节点进行镜像，再将根节点的右节点进行镜像，最后将根节点的左右指针进行交换即可

0 赞同 0 条回复

AD钙奶普通 2023年7月15日下午3:55

翻转二叉树
可以先翻转，再递归子树；也可以先递归子树，再翻转
区别只是在于遍历的顺序，贴出来的做法是后序遍历。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode leftMirror = mirrorTree(root.left);
        TreeNode rightMirror = mirrorTree(root.right);
        reverse(root);
        return root;
    }
    public void reverse(TreeNode node)  {
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
    }
}

0 赞同 0 条回复

June 普通 2023年7月15日下午2:55

/**
 * 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 newRoot = new TreeNode(root.val);
        CopyTree(root,newRoot);
        return newRoot;
    }

    public void CopyTree(TreeNode node,TreeNode newNode)
    {// 递归遍历复制

        if(node.left != null)
        {
            TreeNode right = new TreeNode(node.left.val);
            newNode.right = right;
            CopyTree(node.left,right);
        }
        else
            newNode.right = null;

        if(node.right != null)
        {
            TreeNode left = new TreeNode(node.right.val);
            newNode.left = left;
            CopyTree(node.right,left);
        }
        else
            newNode.left = null;
    }
}

0 赞同 0 条回复

Mooby 普通 2023年7月15日下午1:26

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

0 赞同 0 条回复

波雅汉库克普通 2023年7月15日上午11:40

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

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

0 赞同 0 条回复

艺普通 2023年7月14日下午11:51

“`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 NULL;
}
TreeNode* l = mirrorTree(root->left);
TreeNode* r = mirrorTree(root->right);
root->left = r;
root->right = l;
return root;
}
};
“`
时间复杂度:O(n)
空间复杂度:O(n)

0 赞同 0 条回复

普通 2023年7月14日下午10:23

c++代码
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root)
{
return rootNULL?NULL:new TreeNode(root->val,mirrorTree(root->right),mirrorTree(root->left));
}
};

0 赞同 0 条回复

#00456B 普通 2023年7月14日下午10:14

//方法一 分解问题
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root == NULL){
            return NULL;
        }
        TreeNode* leftTree = mirrorTree(root->left);
        TreeNode* rightTree = mirrorTree(root->right);
        root->left = rightTree;
        root->right = leftTree;
        return root;
    }
};

//方法二 遍历
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        traverse(root);
        return root;
    }
    TreeNode* traverse(TreeNode* root){
        if(root == NULL){
            return NULL;
        }
        swap(root->left, root->right);
        traverse(root->left);
        traverse(root->right);
        return root;
    }
};

0 赞同 0 条回复

阿尚普通 2023年7月14日下午7:58

//翻转二叉树
//方法一
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return root;

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

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

        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;

        // 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
        return root;
    }
}

0 赞同 0 条回复

CaCO3 永久会员 2023年7月14日下午7:34

”’java
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root null){
return null;
}
//交换左右结点
root.left = mirrorTree(root.left);
root.right = mirrorTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;

}
”’
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

CKX 普通 2023年7月14日下午5:22

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }

    left := mirrorTree(root.Left)
    right := mirrorTree(root.Right)
    root.Left = right
    root.Right = left
    return root
}

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

0 赞同 0 条回复

Luminous 普通 2023年7月14日下午5:10

/**
 * 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) {
        reverse(root);
        return root;
    }

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

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

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月14日下午4:44

// C++实现
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 条回复

ONE PIECE 普通 2023年7月14日下午4:38

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

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月14日下午4:36

class Solution {
public TreeNode mirrorTree(TreeNode root) {
//交换左右子树
if(rootnull)
{
return root;
}
mirrorTree(root.left);
mirrorTree(root.right);
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
return root;

}

0 赞同 0 条回复

Recluse 普通 2023年7月14日下午3:36

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

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

0 赞同 0 条回复

V2ero 普通 2023年7月14日下午2:46

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

function mirrorTree(root: TreeNode | null): TreeNode | null {
    if(!root){
        return null
    }
    const left = mirrorTree(root.left);
    const right = mirrorTree(root.right);
    root.left = right;
    root.right = left;
    return root
};

0 赞同 0 条回复

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

共以下 36 个回答

# 回答此问题取消回复

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

共以下 36 个回答

# 回答此问题 取消回复

# 回答此问题取消回复