Leetcode -- 226. Invert Binary Tree(Recur + Itera)

226. Invert Binary Tree(Recur + Itera)
easy
https://leetcode.com/problems/invert-binary-tree/?tab=Description

Invert a binary tree.

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

to

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

思路1： Recursion - when meeting null or leaf nodes, we don't swap.
           Then we keep swaping the left subtree and right subtree (1. traverse 2. reassign value)
Complexity: time O(N) space O(H)
        

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

思路2： Iteration - level order traverse. keep swaping left child and right child of current node

public TreeNode invertTree(TreeNode root) {
        if(root == null)return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode cur = q.poll();
            TreeNode left = cur.left;
            TreeNode right = cur.right;
            cur.left = right;
            cur.right = left;
            if(right != null)q.offer(right);//here order not matter
            if(left != null)q.offer(left);
        }
        return root;
    }