二叉树的镜像

1. 后序遍历的思想

采用递归算法实现交换二叉树的左、右子树，首先交换根结点的左孩子的左、右子树，然后交换根结点

的右孩子的左、右子树，最后交换根结点的左、右孩子，当结点为空时，递归结束。

public void Mirror(TreeNode root)
	{
		TreeNode tmp = null;
		if (root != null)
		{
			Mirror(root.left); // 递归交换左子树
			Mirror(root.right); // 递归交换右子树
			// 交换左、右孩子结点
			tmp = root.left;
			root.left = root.right;
			root.right = tmp;
		}
			
	}

2. 先序遍历思想

	public void Mirror(TreeNode root)
	{
		if (root == null)
			return;
		// 叶子结点
		if (root.left == null && root.right == null)
			return;
		// 交换左右孩子结点
		TreeNode pTemp = root.left;
		root.left = root.right;
		root.right = pTemp;
		
		// 左子树不为空，递归交换左子树
		if (root.left != null)
			Mirror(root.left);
		
		// 右子树不为空，递归交换右子树
		if (root.right != null)
			Mirror(root.right);
	}

3.  层次遍历思想

public void Mirror(TreeNode root)
	{
		if (root == null)
			return;
		
		// 初始化一个队列
		Queue<TreeNode> queue = new LinkedBlockingQueue<>();
		// 根结点入队列
		queue.add(root);
		// 队列不为空
		while (!queue.isEmpty())
		{
			TreeNode node = queue.poll();
			// 交换该结点的左右孩子结点
			if (node.left != null || node.right != null)
			{
				TreeNode tmp = node.left;
				node.left = node.right;
				node.right = tmp;
			}
			// 左子树不为空，则左子树入队列
			if (node.left != null)
				queue.add(node.left);
			// 右子树不为空，则右子树入队列
			if (node.right != null)
				queue.add(node.right);
		}
	}

改成用栈也可以。（先根，再右子树，最后左子树）

public void Mirror(TreeNode root)
	{
		if (root == null)
			return;
		
		// 初始化一个栈
		Stack<TreeNode> s = new Stack<TreeNode>();
		// 根结点入栈
		s.push(root);
		
		// 栈不空
		while (!s.empty())
		{
			TreeNode node = s.pop();
			if (node.left != null || node.right != null)
			{
				TreeNode tmp = node.left;
				node.left = node.right;
				node.right = tmp;
			}
			
			if (node.left != null)
				s.push(node.left);
			if (node.right != null)
				s.push(node.right);
		}
	}