Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
解题思路：
直接获取根节点的左右节点，然后进行交换即可。方法一直接进行交换，方法二使用二叉树层次遍历，话不多说直接上代码。
方法一代码：
public TreeNode invertTree(TreeNode root){if (root==null){return null;}TreeNode left=root.left;TreeNode right=root.right;root.left=invertTree(right);root.right=invertTree(left);return root;}
方法二代码：
public static TreeNode invertTree1(TreeNode root){if(root == null){return null;}Queue<TreeNode> queue = new LinkedList<TreeNode>();//向列队中添加元素queue.offer(root);while(!queue.isEmpty()){//获取并移出元素TreeNode node = queue.poll();TreeNode left = node.left;node.left = node.right;node.right = left;if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}return root;}
列队说明：队列是一种特殊的线性表，它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。
在java5中新增加了java.util.Queue接口，，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。如果要使用前端而不移出该元素，使用element()或者peek()方法。
阳光总在风雨后。只有坚强的忍耐顽强的奋斗，
