剑指offer系列——18.二叉树的镜像/翻转二叉树

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

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

A:
递归完成

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

2.利用栈遍历树的所有节点 node ，并交换每个 node 的左 / 右子节点。

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(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;
    }
}

3. 利用队列遍历树的所有节点 node ，并交换每个 node 的左 / 右子节点。

    public TreeNode mirrorTree(TreeNode root) {
        Queue <TreeNode> qu=new LinkedList<TreeNode>();
        if(root!=null){
            qu.offer(root);
            while(qu.size()!=0){
                TreeNode node=qu.poll();
                TreeNode temp=node.left;
                node.left=node.right;
                node.right=temp;
                if(node.left!=null)
                    qu.offer(node.left);
                if(node.right!=null)
                    qu.offer(node.right);
            }
        }
        return root;
    }