【剑指Offer学习】【面试题19 :二叉树的镜像】[通俗易懂]

2022-07-10 13:09:29 浏览数 (1)

大家好,又见面了,我是全栈君。

题目:请完毕一个函数,输入一个二叉树,该函数输出它的镜像。


二叉树结点的定义:

代码语言:javascript复制
/** * 二叉树的树结点 */
public static class BinaryTreeNode {
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

解题思路:

我们先前序遍历这棵树的每一个结点。假设遍历到的结点有子结点。就交换它的两个子结点。当交换全然部非叶子结点的左右子结点之后。就得到了树的镜像。

代码实现:

代码语言:javascript复制
public class Test19 {
    /** * 二叉树的树结点 */
    public static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;
    }

    /** * 请完毕一个函数,输入…个二叉树。该函数输出它的镜像 * * @param node 二叉树的根结点 */
    public static void mirror(BinaryTreeNode node) {
        // 假设当前结点不为空则进行操作
        if (node != null) {
            // 以下是交换结点左右两个子树
            BinaryTreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;

            // 对结点的左右两个子树进行处理
            mirror(node.left);
            mirror(node.right);
        }
    }

    public static void printTree(BinaryTreeNode node) {
        if (node != null) {
            printTree(node.left);
            System.out.print(node.value   " ");
            printTree(node.right);
        }
    }

    public static void main(String[] args) {
        // 8
        // / 
        // 6 10
        // /  / 
        // 5 7 9 11
        BinaryTreeNode root = new BinaryTreeNode();
        root.value = 8;
        root.left = new BinaryTreeNode();
        root.left.value = 6;
        root.left.left = new BinaryTreeNode();
        root.left.left.value = 5;
        root.left.right = new BinaryTreeNode();
        root.left.right.value = 7;
        root.right = new BinaryTreeNode();
        root.right.value = 10;
        root.right.left = new BinaryTreeNode();
        root.right.left.value = 9;
        root.right.right = new BinaryTreeNode();
        root.right.right.value = 11;
        printTree(root);
        System.out.println();
        mirror(root);
        printTree(root);
        // 1
        // /
        // 3
        // /
        // 5
        // /
        // 7
        // /
        // 9
        BinaryTreeNode root2 = new BinaryTreeNode();
        root2.value = 1;
        root2.left = new BinaryTreeNode();
        root2.left.value = 3;
        root2.left.left = new BinaryTreeNode();
        root2.left.left.value = 5;
        root2.left.left.left = new BinaryTreeNode();
        root2.left.left.left.value = 7;
        root2.left.left.left.left = new BinaryTreeNode();
        root2.left.left.left.left.value = 9;
        System.out.println("n");
        printTree(root2);
        System.out.println();
        mirror(root2);
        printTree(root2);

        // 0
        // 
        // 2
        // 
        // 4
        // 
        // 6
        // 
        // 8
        BinaryTreeNode root3 = new BinaryTreeNode();
        root3.value = 0;
        root3.right = new BinaryTreeNode();
        root3.right.value = 2;
        root3.right.right = new BinaryTreeNode();
        root3.right.right.value = 4;
        root3.right.right.right = new BinaryTreeNode();
        root3.right.right.right.value = 6;
        root3.right.right.right.right = new BinaryTreeNode();
        root3.right.right.right.right.value = 8;
        System.out.println("n");
        printTree(root3);
        System.out.println();
        mirror(root3);
        printTree(root3);


    }
}

执行结果:

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/115522.html原文链接:https://javaforall.cn

0 人点赞