二叉树的镜像

题目链接：https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/

image.png

题目解析

1. 采用递归思路,不要想的太复杂，镜像操作是mirrorTree,具体的实现是root.left等于root.right的值，但是root.right的值也需要进行镜像操作,所以root.left = mirrorTree(root.right);,在同理赋值root.right即可。

public TreeNode mirrorTree(TreeNode root) {
        if (root==null){
            return null;
        }
        TreeNode temp = root.left;
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(temp);
        return root;
 }

复杂度分析
空间复杂度: O(N)。
时间复杂度: O(N)。

2. 采用栈辅助,先放入node的左右节点，在进行单个node左右节点交换。不断的放入数据和取出数据进行交换即可。

public TreeNode mirrorTree(TreeNode root) {
        if (root==null){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            if (node.left!=null) {
                stack.add(node.left);
            }
            if (node.right!=null) {
                stack.add(node.right);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }

复杂度分析
空间复杂度: O(N)。
时间复杂度: O(N)。