226. 翻转二叉树

翻转一棵二叉树。 示例： 输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1 备注:这个问题是受到 Max Howell 的 原问题 启发的 ： 谷歌：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。

解题思路

递归：
自底向上的交换左右子树
左右孩子都有，交换左右子树
只有左孩子，把左孩子变成右孩子
只有右孩子，把右孩子变成左孩子**

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        /*
            自底向上的交换左右子树
            左右孩子都有，交换左右子树
            只有左孩子，把左孩子变成右孩子
            只有右孩子，把右孩子变成左孩子
        */
        if(root == NULL)
            return NULL;
        invertTree(root->left);
        invertTree(root->right);
        if(root->left != NULL || root->right !=NULL){
             TreeNode*temp = root->left;
             root->left = root->right;
             root->right =temp;
        }
        else if(root->left != NULL || root->right == NULL){
            root->right = root->left;
            root->left = NULL;
         }
        else if(root->right != NULL || root->left == NULL){
            root->left = root->right;
            root->right = NULL;
         }
         return root;
    }
};