LeetCode226.翻转二叉树-递归法

226.翻转二叉树

　　题目：输入二叉树根节点，把整棵树镜像翻转

　　思路：将树的每个节点的左右节点交换，本质是二叉树的递归遍历

解1：递归-前序

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        swap(root->left, root->right);  //交换当前节点左右孩子节点 
        invertTree(root->left); //处理左子节点
        invertTree(root->right); //处理右子节点
        return root;
    }
};

解2：递归-后序

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left); //处理左子节点
        invertTree(root->right); //处理右子节点
        swap(root->left, root->right);  //交换当前节点左右孩子节点 
        return root;
    }
};

递归法的中序遍历不行：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) return root;
        invertTree(root->left); //处理左子节点  
        swap(root->left, root->right); //交换当前节点左右孩子节点 
        invertTree(root->right); //处理右子节点
        return root;
    }
};

用一个例子说明：

对比原先的树发现：2节点的孩子1,3翻转了两次，而对7节点没处理