美文网首页剑指offer
二叉树的镜像

二叉树的镜像

作者: G_uest | 来源:发表于2019-07-25 23:30 被阅读0次

    题目来源: 牛客网--二叉树的镜像

    题目描述

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

    输入描述

    二叉树的镜像定义:
    源二叉树 :
                8
               /  \
              6   10
             / \  / \
            5  7 9 11
    镜像二叉树:
                8
               /  \
              10   6
             / \  / \
            11 9 7  5
    

    解题思路

    首先要了解递归,理解节点之间是怎么相互链接的。 (递归不要想太深,只看眼前这一步,逐级向下带入,直到最终出口,再逐级向上回代执行。)

    本题:遍历所有节点,每一个节点都判断是否为 null,不为 null 就说明此节点存在,然后直接互换左右子节点。对子节点进行判断,如果子节点为 null,就不进行递归,如果不为 null 就进行递归。(这样的好处是可以减少一层递归)

    java代码

    提交的代码

    public void Mirror(TreeNode root) {
        // 判断节点是否存在。
        if (root == null) {
            return;
        }
        // 交换左右子节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 判断左右节点是否存在,这样就少递归一层
        if (root.left != null) {
            Mirror(root.left);
        }
        if (root.right != null) {
            Mirror(root.right);
        }
    }
    

    本地测试代码

    import java.util.Scanner;
    
    public class mirrorTreeNode {
            
        public static void main(String[] args) {
            TreeNode root = new TreeNode(8);
            // 生成测试 二叉树
            input(root);
            // 输出原始 二叉树 
            output(root);
            // 二叉树镜像反转
            mirror(root);
            System.out.println("\n");
            // 输出原始二叉树的 镜像
            output(root);
            
        }
        
        // 因为嫌麻烦就把二叉树测试用例写死了
        static void input(TreeNode root) {
            TreeNode fl = new TreeNode(6);
            TreeNode fr = new TreeNode(10);
            TreeNode sl = new TreeNode(5);
            TreeNode sr = new TreeNode(7);
            root.left = fl;
            root.right = fr;
            
            fl.left = sl;
            fl.right = sr;
            
        }
        
        // 输出函数,前序遍历(根节点最先,然后同级先左后右)
        static void output(TreeNode root) {
            System.out.print(root.val + "   ");
            if (root.left != null) {
                output(root.left);
            }
            if (root.right != null) {
                output(root.right);
            }
        }
        
        // 二叉树镜像函数
        public static void mirror(TreeNode root) {
            if (root == null) {
                return;
            }
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            if (root.left != null) {
                mirror(root.left);
            }
            if (root.right != null) {
                mirror(root.right);
            }
        }
    
    }
    
    /**
     * 定义一个二叉树
     */
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
        }
    
    }
    
    

    相关文章

      网友评论

        本文标题:二叉树的镜像

        本文链接:https://www.haomeiwen.com/subject/ftllrctx.html