首页 > 试题广场 >

二叉树的镜像

[编程题]二叉树的镜像

热度指数：151605 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

操作给定的二叉树，将其变换为源二叉树的镜像。

数据范围：二叉树的节点数 $0 \le n \le 1000$ ，二叉树每个节点的值 $0\le val \le 1000$

要求：空间复杂度 $O(n)$ 。本题也有原地操作，即空间复杂度 $O(1)$ 的解法，时间复杂度 $O(n)$

比如：

源二叉树

镜像二叉树

示例1

输入

{8,6,10,5,7,9,11}

输出

{8,10,6,11,9,7,5}

说明

如题面所示

示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Java

木析

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null)
            return pRoot;
        TreeNode left=Mirror(pRoot.left);
        TreeNode right=Mirror(pRoot.right);
        pRoot.left=right;
        pRoot.right=left;
        return pRoot;
    }
}

发表于 2021-03-13 11:25:39 回复(0)

C++

Spectre_

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    TreeNode* Mirror(TreeNode* pRoot) {
        // 时间复杂度O(N)，空间复杂度O(N)
        if (pRoot == nullptr) return nullptr;
        TreeNode *tmp = pRoot->left;
        pRoot->left = Mirror(pRoot->right);
        pRoot->right = Mirror(tmp);
        return pRoot;
    }
};

发表于 2022-08-20 14:08:23 回复(0)

Python 3

来个offer叭！

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

发表于 2022-07-21 19:33:54 回复(0)

Java

NorthXwind

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        // 思路 从底层交换 
        if(pRoot == null){
            return null;
        }
        TreeNode left = Mirror(pRoot.left);
        TreeNode right = Mirror(pRoot.right);
        pRoot.left = right;
        pRoot.right = left;
        return pRoot;
    }
}

发表于 2022-06-03 18:08:00 回复(0)

C++

牛客503684343号

//递归
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==NULL)
            return NULL;
        TreeNode*p =pRoot->right;
        pRoot->right=pRoot->left;
        pRoot->left=p;
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        return pRoot;
        
        
    }

//非递归
    TreeNode* Mirror(TreeNode* pRoot) {
        // write code here
        if(pRoot==NULL)
            return NULL;
        stack<TreeNode*>st;
        st.push(pRoot);
        while(!st.empty())
        {
            TreeNode*top = st.top();
            st.pop();
            TreeNode*p=top->right;
            top->right = top->left;
            top->left=p;
            if(top->right!=NULL)
            {
                st.push(top->right);
            }
            if(top->left!=NULL)
            {
                st.push(top->left);
            }
        }
        return pRoot;
        
    }

发表于 2022-03-30 16:02:04 回复(0)

Java

佞佞佞佞佞佞

public TreeNode Mirror (TreeNode pRoot) {
    if (pRoot == null) return null;
    TreeNode temp = Mirror(pRoot.left);
    pRoot.left = Mirror(pRoot.right);
    pRoot.right = temp;
    return pRoot;
}

发表于 2021-12-10 12:25:51 回复(0)

Python 3

握着我的抱枕

标题 python递归解法

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        # write code here
        if not pRoot:return
        tmp=self.Mirror(pRoot.left)
        pRoot.left=self.Mirror(pRoot.right)
        pRoot.right=tmp
        return pRoot

发表于 2021-11-03 01:54:53 回复(0)

Java

624huiguorou

二叉树的镜像

交换每个节点的左右子树。

考虑叶子节点都为null或者一个为null的情况，

这个代码也可以处理好。

因为pRoot始终不是null，所以没有问题。

public TreeNode Mirror (TreeNode pRoot) {
        //叶子节点都为null或有一个为null都可以处理。
        //因为pRoot不为null，没有问题。
        if(pRoot != null){
            TreeNode temp = pRoot.left;
            pRoot.left = pRoot.right;
            pRoot.right = temp;
            Mirror(pRoot.left);
            Mirror(pRoot.right);
        }
        return pRoot;
}

发表于 2021-08-22 16:19:24 回复(1)

Java

QAQWQAQ

    public TreeNode Mirror(TreeNode pRoot) {

        if (pRoot == null) return null;

        //左右节点交换
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;

        Mirror(pRoot.left);
        Mirror(pRoot.right);

        return pRoot;
    }

发表于 2021-08-15 18:08:08 回复(0)

C++

墨雨云烟

    TreeNode* Mirror(TreeNode* pRoot)
    {
        if(pRoot == NULL)
            return pRoot;
        
        TreeNode *tmp = pRoot->left;
        pRoot->left = pRoot->right;
        pRoot->right = tmp;
        
        Mirror(pRoot->left);
        Mirror(pRoot->right);
        
        return pRoot;
    }//递归

发表于 2021-07-17 08:33:03 回复(0)

Java

千里马不常有

首先，看到二叉树，那么就马上想到，可以用递归

其次，要找到递归终止的条件

最后，完成一次操作逻辑，并且重复下去

本题代码

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        //使用递归
        //递归的结束条件是，当前节点为空,或者是交换完成
        //所谓交换，那必然就是三步法
        if(pRoot==null) return null;
        TreeNode tmp = pRoot.left;
        pRoot.left=Mirror(pRoot.right);
        pRoot.right=Mirror(tmp);
        
        return pRoot;
    }
}

发表于 2021-05-03 09:43:01 回复(0)

◤特种⌒核桃◥

来个python的非递归版本（借助队列）：

class Solution:
    def Mirror(self , pRoot ):
        if not pRoot: return pRoot
        q = []  #队列
        q.append(pRoot)
        root = pRoot
        while q:
            pRoot=q.pop(0)
            pRoot.left,pRoot.right=pRoot.right,pRoot.left
            if pRoot.left:
                q.append(pRoot.left)
            if pRoot.right:
                q.append(pRoot.right)
        return root

发表于 2021-04-26 22:06:26 回复(0)

JavaScript

IPzzzi

function Mirror( pRoot ) {
    // write code here
    if(pRoot == null){
        return pRoot;
    }
//     var temp = pRoot.left;
//     pRoot.left = pRoot.right;
//     pRoot.right = temp;
    [pRoot.left,pRoot.right] = [pRoot.right,pRoot.left];
    Mirror(pRoot.left);
    Mirror(pRoot.right);
    return pRoot;
}

发表于 2021-03-26 14:51:36 回复(0)

西南交大巨可爱

#Python 使用递归法完成
class Solution:
    def Mirror(self , pRoot ):
        # write code here
        if not pRoot: return 
        if pRoot.left&nbs***bsp;pRoot.right:
            pRoot.left, pRoot.right = pRoot.right, pRoot.left
            self.Mirror(pRoot.left)
            self.Mirror(pRoot.right)
        return pRoot

发表于 2021-03-10 15:30:17 回复(0)

Python

食堂在逃干饭王

递归

class Solution:
    def Mirror(self , pRoot ):
        if pRoot == None:
            return None
        pRoot.left, pRoot.right = pRoot.right, pRoot.left
        pRoot.left = self.Mirror(pRoot.left)
        pRoot.right = self.Mirror(pRoot.right)
        return pRoot

发表于 2021-03-01 14:42:42 回复(1)

Java

杀死那只大白鹿

# 先交换左右子节点，再处理左右子树

  public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if(pRoot==null)return null; //边界处理
        //左右 对称当前左右子节点
        if(pRoot.left!=null || pRoot.right!=null){
            TreeNode  temp =pRoot.left;
            pRoot.left  =pRoot.right ;
            pRoot.right =temp;
            //对子结构进行反转
            Mirror(pRoot.left);
            Mirror(pRoot.right);
        }
        return pRoot;
    }

发表于 2021-02-25 23:29:05 回复(0)

HelloW1

##采用递归思想##
1.先处理根节点。若根节点为空，或为单个节点，则直接返回。否则交换左右节点
2.处理根节点的左子树
3.处理根节点的右子树

import java.util.*;

public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null)
            return pRoot;
        if(pRoot.left==null && pRoot.right==null)
            return pRoot;
        //处理根节点，交换左右节点
        TreeNode temp=pRoot.left;
        pRoot.left=pRoot.right;
        pRoot.right=temp;
        //处理左子树
        Mirror(pRoot.left);
        //处理右子树
        Mirror(pRoot.right);
        return pRoot;
    }
}

发表于 2021-02-26 23:39:25 回复(2)

保洁大哥

递归解决，先遍历左子树，交换左右孩子，然后遍历右子树，交换左右孩子，类似于后序遍历

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return TreeNode类
#
class Solution:
    
    def Mirror(self , pRoot ):
        if pRoot:
            right = self.Mirror(pRoot.left)
            left = self.Mirror(pRoot.right)
            pRoot.right = right
            pRoot.left = left
            return pRoot
        # write code here

发表于 2021-03-03 08:39:32 回复(2)

C/C++

BrainerGao

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return TreeNode类
 */
struct TreeNode* Mirror(struct TreeNode* pRoot ) {
    if (pRoot == NULL) {
        return NULL;
    }
    struct TreeNode* tmp = pRoot->left;
    pRoot->left = pRoot->right;
    pRoot->right = tmp;
    Mirror(pRoot->left);
    Mirror(pRoot->right);
    return pRoot;
}

编辑于 2021-02-28 15:23:50 回复(0)

Java

WhyNot??

Java递归解法

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        //如果树是空的，直接返回空结点
        if(pRoot == null){
            return pRoot;
        }
        //如果只有根节点，直接返回根节点
        if(pRoot.left==null && pRoot.right == null) return pRoot;
        //交换结点
        TreeNode temp = pRoot.right;
        pRoot.right = pRoot.left;
        pRoot.left = temp;
        //进入递归
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

编辑于 2021-05-28 13:29:39 回复(0)

提交观点

问题信息

树

上传者：牛客301499号

难度：

267条回答 927收藏 10213浏览

通过挑战的用户

查看代码

李逢溪

2023-03-13 10:59:20
皇家化院

2023-02-26 14:36:20
随机昵称都有什...

2023-02-21 17:20:26
讲义气的山羊希...

2023-02-16 11:18:43
侬是一个好人

2023-02-03 14:58:05

二叉树的镜像

输入

输出

说明

输入

输出

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

标题 python递归解法

# 先交换左右子节点，再处理左右子树

问题信息

热门推荐

通过挑战的用户

相关试题