LeetCode 剑指Offer 面试题27. 二叉树的镜像

手撕代码八百里

发布于 2020-07-28 22:12:33

2970

发布于 2020-07-28 22:12:33

文章被收录于专栏：猿计划

文章目录

一、面试题27. 二叉树的镜像
二、解题
- （一）非递归方式
- （二）递归方式
三、小郑有话说

一、面试题27. 二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

镜像输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

示例 1：

输入：root = [4,2,7,1,3,6,9] 输出：[4,7,2,9,6,3,1]

二、解题

这个题很直白的就是反转二叉树

（一）非递归方式

package tree.二叉树的镜像;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Auther: truedei
 * @Date: 2020 /20-6-10
 * @Description: 二叉树镜像
 */
public class Solution {

    static public TreeNode mirrorTree(TreeNode root) {

        if(root==null)
            return null;

        LinkedList<TreeNode> queue = new LinkedList<>();

        queue.add(root);

        TreeNode gen = new TreeNode(root.val);

        while (!queue.isEmpty()){
			
			//交换位置
            TreeNode node = queue.pop();
            TreeNode temp = node.left;
            node.left= node.right;
            node.right = temp;

            if(node.left!=null)
                queue.add(node.left);

            if(node.right!=null)
                queue.add(node.right);


        }

        return root;
    }


    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(4);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(7);
        TreeNode t4 = new TreeNode(1);
        TreeNode t5 = new TreeNode(3);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(9);


        t1.left=t2;
        t1.right=t3;

        t2.left=t4;
        t2.right=t5;

        t3.left=t6;
        t3.right=t7;

        TreeNode treeNode = mirrorTree(t1);
     

    }





}

class TreeNode {
    int val;//每个节点存放的数据
    TreeNode left;//左节点
    TreeNode right;//右节点
    TreeNode(int x) { val = x; }
}

（二）递归方式

 public TreeNode mirrorTree(TreeNode root) {

        //根节点为null时，返回null
        if(root==null)
            return null;

        //当只有根节点时，直接返回
        if(root!=null && root.left==null && root.right==null)
            return root;

        //交换位置
        TreeNode temp = root.left;
        root.left=root.right;
        root.right=temp;


        if(root.left!=null)
            mirrorTree(root.left);

        if(root.right!=null)
            mirrorTree(root.right);

        return root;
    }