226. Invert Binary Tree

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

Input:
     4
   /     2     7
 / \   / 1   3 6   9
Output:
     4
   /     7     2
 / \   / 9   6 3   1

// bfs 
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
      Deque<TreeNode> queue = new ArrayDeque<>();
      if(root != null){
        queue.offer(root);
      }
      
      while(!queue.isEmpty()){
        TreeNode cur = queue.poll();
        TreeNode left = cur.left;
        cur.left = cur.right;
        cur.right = left;
        
        if(cur.left != null){
          queue.offer(cur.left);
        }
        
        if(cur.right != null){
          queue.offer(cur.right);
        }
      }
      return root;
        
    }
}