leetcode Question: Invert Binary Tree

Invert Binary Tree

Invert a binary tree.

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

to

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

Analysis:

This is an easy question if you are familiar with recursion or DFS.
At the first glance, it is very natural to think this as an BFS problem, where we can search the tree level by level. However, if the binary tree is not a full tree, there might be many problems.
So, let's do it in simple recursion.

In my word, recursion always requires two things to consider, one is condition, the other is sub-problem. Condition mean stop/termination condition, e.g., in this question, when we meets the NULL node, we have to stop. When the left tree is NULL, the after converting, right is NULL, and vice versa.  Sub-problem is to find out how the program (the recursion function) can iterate many times. In this question, for each node, we just do the same process, find the left node,  find the right node, and swap them. But before this process, (this is the key part in recursion) we have to make sure that the left node and right node are already converted. See line 20 and line 26 in the C++ code below.  Getting clear that how those two things, writing program only requires some minor considerations such as the return value and null pointers, etc. 



Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root){
            return NULL;
        }
        
        TreeNode* res = new TreeNode(root->val); 
        
        if (root->right){
            res->left = invertTree(root->right);
        }else{
            res->left = NULL;
        }
        
        if (root->left){
            res->right = invertTree(root->left);
        }else{
            res->right = NULL;
        }
        
        return res;
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        
        res = TreeNode(root.val)
        if root.right:
            res.left = self.invertTree(root.right)
        else:
            res.left = None
        
        if root.left:
            res.right = self.invertTree(root.left)
        else:
            res.right = None
            
        return res