10.Invert Binary Tree

Input:

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

Output:

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

Solution: (Using Level Order Traversal)

class Solution
{
public:
    TreeNode *invertTree(TreeNode *root)
    {
        
        if(root == NULL)
        {
            return NULL;
        }

        queue<TreeNode *> q;

        q.push(root);

        TreeNode *t = NULL;

        while (!q.empty())
        {

            t = q.front();
            q.pop();

            swap(t->left, t->right);

            if (t->left)
            {
                q.push(t->left);
            }

            if (t->right)
            {
                q.push(t->right);
            }
        }

        return root;
    }
};

Solution: (Recursion)

class Solution
{
public:
    void invert(TreeNode *&root)
    {

        swap(root->left, root->right);

        if (root->left)
        {
            invert(root->left);
        }

        if (root->right)
        {
            invert(root->right);
        }

        return;
    }

    TreeNode *invertTree(TreeNode *root)
    {

        if (!root)
        {
            return root;
        }

        invert(root);

        return root;
    }
};