首页 > 试题广场 >

二叉树的镜像

[编程题]二叉树的镜像

热度指数：133762 时间限制：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) {
        // write code here
        if (pRoot != null) {
            TreeNode left = pRoot.left;
            pRoot.left = Mirror(pRoot.right);
            pRoot.right = Mirror(left);
            return pRoot;
        } else {
            return pRoot;
        }
    }
}

编辑于 2024-03-28 10:30:02 回复(0)

Java

牛客839384289号

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

编辑于 2024-03-10 16:22:33 回复(0)

Java

alyxe1

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 null;
        
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

编辑于 2024-01-21 09:15:18 回复(0)

Java

fash1on

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

发表于 2023-11-09 19:56:53 回复(0)

Java

牛客920655150号

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    TreeNode t;
    public TreeNode Mirror (TreeNode pRoot) {
        //只需要每次递归时把该节点的左右节点交换位置即可
        a(pRoot);
        return pRoot;
    }
    public void a(TreeNode root) {
        if(root==null)
            return;
        t=root.left;
        root.left=root.right;
        root.right=t;
        a(root.left);
        a(root.right);
    }
}

发表于 2023-10-12 14:03:30 回复(0)

Java

dqxfz

public TreeNode Mirror (TreeNode pRoot) {

if (pRoot == null) {

return null;

}

TreeNode tmpL = pRoot.left;

pRoot.left = Mirror(pRoot.right);

pRoot.right = Mirror(tmpL);

return pRoot;

}

发表于 2023-09-20 21:17:00 回复(0)

Java

秃驴应该痛

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot==null||(pRoot.left==null&&pRoot.right==null)) {
            return pRoot;
        }
        Mirror(pRoot.left);
        TreeNode tmp=pRoot.left;
        pRoot.left=pRoot.right;
        pRoot.right=tmp;
        Mirror(pRoot.left);//注意因为是把左右子树进行的交换，所以这里往下递归的还是left
        return pRoot;
    }
}

发表于 2023-07-15 20:44:11 回复(0)

Java

做则必成的勇气和信心

public TreeNode Mirror (TreeNode pRoot) {
        //带swap的先序遍历
        if(pRoot==null) return pRoot;
        build(pRoot);
        return pRoot;
    }
    public void build(TreeNode pRoot){
        if(pRoot==null) return;
        //先序遍历
        TreeNode tmp=pRoot.left;
        pRoot.left=pRoot.right;
        pRoot.right=tmp;
        build(pRoot.left);
        build(pRoot.right);
    }

发表于 2023-07-12 11:59:42 回复(0)

Java

牛客928243408号

不追求O1复杂度， O1需要魔改mirrors才有可能实现，至少是困难+的级别。

使用队列 O(N / 2)

import java.util.*;
public class Solution {
    public TreeNode Mirror (TreeNode root) {
        if (root == null) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (! queue.isEmpty()) {
            TreeNode curr = queue.poll();
            if (curr.left != null) queue.offer(curr.left);
            if (curr.right != null) queue.offer(curr.right);
            TreeNode temp = curr.left;
            curr.left = curr.right;
            curr.right = temp;
        }
        return root;
    }
}

使用栈 O(H)

import java.util.*;
public class Solution {
    public TreeNode Mirror (TreeNode root) {
        if (root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (! stack.isEmpty()) {
            TreeNode node = stack.pop(), temp = null;
            temp = node.left;
            node.left = node.right;
            node.right = temp;
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        return root;
    }
}

发表于 2022-12-20 04:41:36 回复(0)

Java

ZhanHeng

import java.util.*;

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

    private void preOrder(TreeNode root) {
        if(root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 递归
        preOrder(root.left);
        preOrder(root.right);
    }
}

发表于 2022-11-18 10:55:09 回复(0)

Java

小杨yyy

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
        return exchange(pRoot);
    }
    public TreeNode exchange(TreeNode root){
        //如果根节点为空或者只有根节点，则直接返回
        if(root==null || (root.left==null && root.right==null)){
            return root;
        }
        //创建一个临时节点来更换左右节点
        TreeNode temp=new TreeNode(0);
        temp=root.left;
        root.left=root.right;
        root.right=temp;
        //更换完毕后，递归调用更换函数，逐层递归更换
        exchange(root.left);
        exchange(root.right);
        return root;
    }
}

发表于 2022-11-11 11:25:00 回复(0)

Java

dynamo1

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
        doMirror(pRoot);

        return pRoot;
    }

    private void doMirror(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        doMirror(root.left);
        doMirror(root.right);
    }


}

发表于 2022-11-09 07:29:00 回复(0)

Java

键盘都敲坏了.

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pRoot TreeNode类 
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // 根节点为null，或者根节点没有子树，则返回root
        if(pRoot == null || (pRoot.left ==null &&  pRoot.right == null))  return pRoot;
        
        // 递归进行镜像，每次递归都是树本身的子节点对调
        Mirror (pRoot.left, pRoot.right, pRoot);
        // 返回root
        return pRoot;
    }
    public void Mirror (TreeNode left, TreeNode right, TreeNode pre) {
        // 都为空时 不需要镜像
        if(left == null && right == null) return;
        
        // 左右节点互相交换
        pre.left = right;
        pre.right = left;
        
        // left不为空，则向左子树递归将其子节点镜像
        if(left != null) Mirror (left.left, left.right, left);

        // right不为空，则向右子树 将其子节点镜像
        if(right != null) Mirror (right.left, right.right, right);
    }
}

发表于 2022-11-05 13:03:35 回复(1)

Java

ludvig

public class Solution {

public TreeNode Mirror (TreeNode pRoot) {

if (pRoot == null) {

return null;

}

TreeNode treeNode = new TreeNode(pRoot.val);

treeNode.left = Mirror(pRoot.right);

treeNode.right = Mirror(pRoot.left);

return treeNode;

}

发表于 2022-10-03 14:06:51 回复(0)

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 null;
        TreeNode temp = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = temp;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

发表于 2022-09-29 08:23:58 回复(0)

Java

aklddnddkwndje

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){
            TreeNode l = pRoot.left;
            TreeNode r = pRoot.right;
            pRoot.left = r;
            pRoot.right = l;
            Mirror(l);
            Mirror(r);
        }
        return pRoot;
    }
}

发表于 2022-09-07 09:26:30 回复(0)

Java

牛客571536534号

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

        mirrorDfs(pRoot);
        return pRoot;
    }

    private void mirrorDfs(TreeNode pRoot) {
        if (pRoot == null) {
            return;
        }

        TreeNode cur = pRoot.left;
        pRoot.left = pRoot.right;
        pRoot.right = cur;
        if (pRoot.left != null) {
            mirrorDfs(pRoot.left);
        }

        if (pRoot.right != null) {
            mirrorDfs(pRoot.right);
        }
    }
}

发表于 2022-08-16 17:47:12 回复(0)

提交观点

问题信息

树

上传者：牛客301499号

难度：

76条回答 792收藏 6202浏览

通过挑战的用户

查看代码

李逢溪

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，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题