226 Invert Binary Tree

nvert a binary tree.

     4
   /   
  2     7
 /    / 
1   3 6   9

     4
   /   
  7     2
 /    / 
9   6 3   1
题目含义：左右交换二叉树的节点值
方法一：DFS

1     public TreeNode invertTree(TreeNode root) {
2         if(root==null){
3             return null;
4         }
5         TreeNode newNode = new TreeNode(root.val);
6         newNode.left = invertTree(root.right);
7         newNode.right = invertTree(root.left);
8         return newNode;        
9     }

方法二：BfS

 1     public TreeNode invertTree(TreeNode root) {
 2         if(root==null)return null;
 3         final Queue<TreeNode> queue = new LinkedList<>();
 4         queue.offer(root);
 5         while(!queue.isEmpty()) {
 6             final TreeNode node = queue.poll();
 7             final TreeNode left = node.left;
 8             node.left = node.right;
 9             node.right = left;
10             if(node.left != null) queue.offer(node.left);
11             if(node.right != null) queue.offer(node.right);
12         }
13         return root;
14     }