首页 > 试题广场 >

二叉树的镜像

[编程题]二叉树的镜像
  • 热度指数：144768 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
操作给定的二叉树，将其变换为源二叉树的镜像。
数据范围：二叉树的节点数 ， 二叉树每个节点的值
要求： 空间复杂度 。本题也有原地操作，即空间复杂度 的解法，时间复杂度

比如：
源二叉树
镜像二叉树

示例1

输入

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

输出

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

说明

如题面所示
示例2

输入

{}

输出

{}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息
算法知识视频讲解
添加回答
Javascript
Xinleidebaby头像 Xinleidebaby 
function Mirror( pRoot ) {
    // write code here
    if(!pRoot) return null
    else{
        //先进行交换 ，在进行递归
          [pRoot.right,pRoot.left]=[pRoot.left,pRoot.right]
          Mirror(pRoot.right)
          Mirror(pRoot.left)
    }
    return pRoot
}

发表于 2022-08-02 11:34:16 回复(0)
Javascript
AAATest头像 AAATest 
function Mirror( pRoot ) {
    // write code here
    if(!pRoot) return null

    let temp = pRoot.left;
    pRoot.left = Mirror(pRoot.right)
    pRoot.right = Mirror(temp)

    return pRoot
}
发表于 2022-03-09 12:09:04 回复(0)
Javascript
nicole27头像 nicole27 
function Mirror( pRoot ) {
    // write code here
    if(pRoot == null) return pRoot;
    let queue = [];
    queue.push(pRoot);
    while(queue.length!==0){
        let node = queue.shift();
     //交换当前节点的左右子树
        if(node!==null){
             let tmp = node.right;
            node.right = node.left;
            node.left = tmp;
            queue.push(node.left);
            queue.push(node.right);
        }
    }
    return pRoot;
}

发表于 2022-03-08 16:01:45 回复(0)
Javascript
天网-__-头像 天网-__-

二叉树的镜像实际上等价于二叉树所有的子节点左右交换就可以。

function Mirror( pRoot ) {
    if (!pRoot) return pRoot;
    const dfs = (node) => {
        if (!node) return node;
        dfs(node.left);
        dfs(node.right);
        [node.left, node.right] = [node.right, node.left];
    }
    dfs(pRoot)
    return pRoot;
}
发表于 2021-12-27 14:09:33 回复(0)
Javascript
Elegy201905242021282头像 Elegy201905242021282
function Mirror( pRoot ) {
    if(pRoot) {
        const temp = pRoot.right;
        pRoot.right = pRoot.left;
        pRoot.left = temp;
        Mirror(pRoot.right);
        Mirror(pRoot.left);
        return pRoot
    }
    // write code here
}
发表于 2021-11-24 14:56:55 回复(0)
Javascript
牛客822492274号头像 牛客822492274号
function Mirror( pRoot ) {
    // write code here
    if(pRoot === null){
        return pRoot;
    }
    let left = pRoot.left;
    let right = pRoot.right;
    pRoot.left = Mirror(right);
    pRoot.right = Mirror(left);
    return pRoot;
}
发表于 2021-09-08 19:51:50 回复(0)
Javascript
牛客246205877号头像 牛客246205877号 
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return TreeNode类
 */
function Mirror( pRoot ) {
    if(pRoot){
        let left = pRoot.left;
        let right = pRoot.right;
        if(left || right){
            pRoot.right = left;
            pRoot.left = right;
            if(left) Mirror(left);
            if(right) Mirror(right)
        }
    }
    
    return pRoot
}
module.exports = {
    Mirror : Mirror
};

发表于 2021-09-08 15:45:32 回复(0)
Javascript
webchang头像 webchang
使用JavaScript来实现

思路：关键点在于需要遍历每一个节点，然后交换它的两个子节点，一直循环下去，直到所有的节点都遍历完为止。

方法1

使用一个数组来存储尚未处理的节点 
/*
 * function TreeNode(x) {
 *   this.val = x;
 *   this.left = null;
 *   this.right = null;
 * }
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pRoot TreeNode类 
 * @return TreeNode类
 */
function Mirror( pRoot ) {
    if(pRoot === null) return null;
    
    let arr = [];
    arr.push(pRoot);
    while(arr.length > 0) {
        let node = arr.pop();
        let nodeLeft = node.left;
        node.left = node.right;
        node.right = nodeLeft;
        
        if(node.left) arr.push(node.left);
        if(node.right) arr.push(node.right);
    }
    return pRoot;
}
module.exports = {
    Mirror : Mirror
};

方法2

使用递归 
function Mirror( pRoot ) {
    if(!pRoot) return null;
    let nodeLeft = pRoot.left;
    pRoot.left = pRoot.right;
    pRoot.right = nodeLeft;
    
    Mirror(pRoot.left);
    Mirror(pRoot.right);
    return pRoot;
}

发表于 2021-07-24 17:38:47 回复(0)
JavaScript
pro给一个offer吧头像 pro给一个offer吧 
function Mirror( pRoot ) {
    if(!pRoot) {
        return null;
    }
    let temp = new TreeNode(0);
    temp = pRoot.left;
    pRoot.left = pRoot.right;
    pRoot.right = temp;
    Mirror(pRoot.left);
    Mirror(pRoot.right);
    return pRoot;
}

发表于 2021-07-12 11:10:53 回复(0)
JavaScript
别卷啦！头像 别卷啦！
递归 先交换左右节点 再递归左右子树 
function Mirror( pRoot ) {
    // write code here
    if(pRoot == null) return null;
    [pRoot.left, pRoot.right] = [pRoot.right, pRoot.left]
    Mirror(pRoot.left)
    Mirror(pRoot.right)
    return pRoot
}


编辑于 2021-06-17 12:07:48 回复(0)
JavaScript
NPC201904301802722头像 NPC201904301802722 
function Mirror( pRoot ) {
    // write code here
    if(!pRoot){
        return
    }
    
    Mirror(pRoot.left)
    Mirror(pRoot.right)
    let temp=pRoot.left
    pRoot.left=pRoot.right
    pRoot.right=temp
    
    return pRoot
}

发表于 2021-06-16 00:20:59 回复(0)
JavaScript
IPzzzi头像 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)
JavaScript
splwany头像 splwany 
function Mirror( pRoot ) {
    if (!pRoot) return pRoot;
    [pRoot.left, pRoot.right] = [pRoot.right, pRoot.left];
    Mirror(pRoot.left);
    Mirror(pRoot.right);
    return pRoot;
}

编辑于 2021-03-21 16:52:43 回复(0)
JavaScript
Newman1997头像 Newman1997
树左右子树分别遍历递归的题很常见，注意用temp作为交换地址的中间值 
function Mirror( pRoot ) {
    if(pRoot==null) return null
    nodeChange(pRoot)
    return pRoot
}
function nodeChange(root){
    if(root.left==null && root.right==null) return
    
    var temp=root.left
    root.left=root.right
    root.right=temp
    if(root.left!==null) nodeChange(root.left)
    if(root.right!==null) nodeChange(root.right)
}

发表于 2021-03-03 19:51:37 回复(0)
提交观点

问题信息

树
上传者：牛客301499号
难度：
16条回答 7512浏览

热门推荐

通过挑战的用户

查看代码

相关试题

二叉树的镜像

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号