Leetcode 226: invert binary tree

Invert a binary tree.

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

to

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

关于树的题目， 通过分析题目，很明显这个题目用recursion可以做，

因为对于树上的每一个Node的进行inverse的性质是相同的， 这个题

目recursion的方法很简单，只要将root左右两边的node进行swap就行了。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        //base case
        if (root == NULL) return root;
        TreeNode* helper = root->right;
        root->right = invertTree(root->left);
        root->left = invertTree(helper);
        return root;
    }
}; 

time complexity: O (n)