二叉树的镜像

问题陈述

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

1
2
3
4
5
6
7
8
9
10
11
12
例如输入：
       4
      /  \
     2    7
    /\    /\
   1  3  6  9 
镜像输出：
​      4
​    /   \
    7     2
   / \   / \
  9   6 3   1

思路分析

如何实现镜像反转，其实就是从上到下对每个结点的左右结点进行交换，如果存在左（右）结点一个为空，则同样与空结点进行交换。

考虑栈结构的特性，可以用栈暂存结点。先根结点入栈，当栈不空，定义输出镜像为弹出的栈顶元素。继续，如果根结点的左结点不空，加入左结点；右结点不空，加入右结点。然后实现交换左右结点。

如此，实现。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class BinaryTree_Mirror {
    public TreeNode treeMirror(TreeNode root){
        if(root==null) return null;         //判断树是否为空
        Stack<TreeNode> stack=new Stack<>();//定义类型为TreeNode的栈
        stack.push(root);
        while (!stack.isEmpty()){     //循环输出镜像二叉树元素
            TreeNode node=stack.pop();
            if(node.left!=null) stack.push(node.left);
            if(node.right!=null) stack.push(node.right);
            TreeNode curr=node.left;   //交换左右结点
            node.left=node.right;
            node.right=curr;
        }
        //如果当前结点已经是左叶子，那就是叶子左空结点与有空结点交换，然后wlile判断输出该叶子结点，继续右叶子如此。
        return root;
    }
}