/**

  * Definition for a binary tree node.

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode(int x) { val = x; }

  * }

  */

 public class Solution {

     public TreeNode invertTree(TreeNode root) {

         if (root == null)

             return root;

         TreeNode leftNode = null, rightNode = null;

         if (root.left != null)

             leftNode = invertTree(root.left);

         if (root.right != null)

             rightNode = invertTree(root.right);

         root.left = rightNode;

         root.right = leftNode;

         return root;

     }

 }

 /**

  * Definition for a binary tree node.

  * public class TreeNode {

  *     int val;

  *     TreeNode left;

  *     TreeNode right;

  *     TreeNode(int x) { val = x; }

  * }

  */

 public class Solution {

     public TreeNode invertTree(TreeNode root) {

         if (root == null)

             return root;

         List<TreeNode> current = new ArrayList<TreeNode>();

         List<TreeNode> next;

         current.add(root);

         while (current.size() > 0) {

             next = new ArrayList<TreeNode>();

             for (TreeNode tmpNode : current) {

                 // inverse tmpNode

                 TreeNode left = tmpNode.left;

                 TreeNode right = tmpNode.right;

                 tmpNode.right = left;

                 tmpNode.left = right;

                 if (right != null)

                     next.add(right);

                 if (left != null)

                     next.add(left);

             }

             current = next;

         }

         return root;

     }

 }