剑指offer系列之十七：二叉树的镜像

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。
输入描述:

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

仔细观察原二叉树与镜像二叉树，可以发现镜像二叉树实际上就是把每个节点的左右孩子结点进行了交换，比如在遍历到8这个节点时候，首先交换其左右孩子6和10，其对应的子树也应该进行交换。所以我们可以采用前序遍历的方法进行操作，每当遇到一个结点的时候，首先判断其是否有左右孩子（有其中之一即可），如果有的话，就交换其左右孩子，然后继续遍历其左右子树，只要不为空就继续交换其左右孩子节点（在交换具有孩子结点的结点的时候，其孩子结点也一并被交换了）。下面是基于这种思路的实现代码（已被牛客AC）：

package com.rhwayfun.offer;

import java.util.Stack;

public class TreeMirror {
    //二叉树结点定义
    public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    //采用递归的方式进行交换
    public void Mirror(TreeNode root) {
        if (root == null || (root.left == null && root.right == null))
            return;

        TreeNode nodeTemp = root.left;
        root.left = root.right;
        root.right = nodeTemp;

        if (root.left != null) {
            Mirror(root.left);
        }
        if (root.right != null) {
            Mirror(root.right);
        }
    }

    //采用非递归的方式进行交换
    public void Mirror2(TreeNode root) {
        if (root == null || (root.left == null && root.right == null))
            return;

        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
        while (!s.isEmpty()) {
            TreeNode node = s.pop();
            //交换左右孩子结点
            TreeNode nodeTemp = node.left;
            node.left = node.right;
            node.right = nodeTemp;
            //遍历左子树
            if (node.left != null)
                s.push(node.left);
            //遍历右子树
            if (node.right != null)
                s.push(node.right);
        }
    }

    //前序遍历
    public void preOrderTarverse(TreeNode root) {
        Stack<TreeNode> s = new Stack<TreeNode>();
        while (root != null || !s.isEmpty()) {
            //遍历左子树
            while (root != null) {
                System.out.println(root.val);
                s.push(root);
                root = root.left;
            }
            // 左子树遍历结束，继续遍历右子树
            if (!s.isEmpty()) {
                root = s.pop();
                root = root.right;
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(10);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(9);
        TreeNode node6 = new TreeNode(11);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;

        TreeMirror r = new TreeMirror();
        r.Mirror2(root);

        r.preOrderTarverse(root);
    }
}