Leetcode 227 Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Solution 1: recursive

 public class Solution {  
   public TreeNode invertTree(TreeNode root) {  
     if (root==null) return null;  
     TreeNode left=invertTree(root.left);  
     TreeNode right=invertTree(root.right);  
     root.left=right;  
     root.right=left;  
     return root;  
   }  
 }  

Solution 2: iterative using stack

 public class Solution {  
   public TreeNode invertTree(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     if (root==null) return null;  
     stack.push(root);  
     while (!stack.isEmpty()) {  
       TreeNode x=stack.pop();  
       TreeNode left=x.left;  
       x.left=x.right;  
       x.right=left;  
       if (x.left!=null) stack.push(x.left);  
       if (x.right!=null) stack.push(x.right);  
     }  
     return root;  
   }  
 }  

Solution 3: iterative using queue

 public class Solution {  
   public TreeNode invertTree(TreeNode root) {  
     Queue<TreeNode> qu=new LinkedList<>();  
     if (root==null) return null;  
     qu.offer(root);  
     while (!qu.isEmpty()) {  
       TreeNode x=qu.poll();  
       if (x.left!=null) qu.offer(x.left);  
       if (x.right!=null) qu.offer(x.right);  
       TreeNode left=x.left;  
       x.left=x.right;  
       x.right=left;  
     }  
     return root;  
   }  
 }