# Invert Binary Tree

Easy

## Question

Invert a binary tree.

Example

``````  1         1
/ \       / \
2   3  => 3   2
/       \
4         4
``````

## Challenge

Do it in recursion is acceptable, can you do it without recursion?

## Solution

#### Java (Iterative, passed on leetcode)

``````/**
* 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 || (root.left == null && root.right == null)) {
return root;
}
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode tmp = node.left;
node.left = node.right;
node.right = tmp;
if (node.left != null) {
}
if (node.right != null) {
}
}
return root;
}
}
``````

#### Java (recursive, passed on lintcode)

``````/**
* Definition of TreeNode:
* public class TreeNode {
*     public int val;
*     public TreeNode left, right;
*     public TreeNode(int val) {
*         this.val = val;
*         this.left = this.right = null;
*     }
* }
*/
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void invertBinaryTree(TreeNode root) {