226. 翻转二叉树

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)return root;
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;

        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

这里就是利用的递归的玩法去搞的，交换整个树，那就是把一个节点的左右节点交换了，然后再让左右子树进行整个树的交换。大问题到小问题，小问题到解决问题。

这里有个关键的点就是：先去彻底的理解题目，本质上就是一个节点的两个儿子交换一下，等你所有的节点都整一遍就完成了交换整棵树。所以说，这道题就是考的遍历！

上边的这个分析是非常重要的！因为这就是从业务需求到变成术语需求的转换。

既然是遍历，那就来吧，层序遍历：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)return root;
        queue q;
        q.push(root);
        TreeNode* ans = root;
        while(!q.empty()){
            //由于这里的遍历和层数没啥关系，所以就可以不用写内层的for循环了
            //另外一点就是对于空的子节点也要入队。
            root == q.front();
            q.pop();
            if(root == nullptr)continue;
            TreeNode* temp = root->right;
            root->right = root->left;
            root->left = temp;
            q.push(root->left);
            q.push(root->right);
        }
        return ans;
    }
};

上边是一个错误的死循环的情况。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr)return root;
        queue q;
        q.push(root);
        TreeNode* ans = root;
        while(!q.empty()){
            //由于这里的遍历和层数没啥关系，所以就可以不用写内层的for循环了
            //另外一点就是对于空的子节点也要入队。
            root = q.front();
            q.pop();
            if(root == nullptr){
                continue;
            }
            TreeNode* temp = root->right;
            root->right = root->left;
            root->left = temp;
            q.push(root->left);
            q.push(root->right);
        }
        return ans;
    }
};

上边这个是正确答案！！！

root == q.front();  应该换成root = q.front();

傻逼玩意，如果是前者，root根本不会被赋值！

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack stk;
        TreeNode* ans = root;
        if(root == nullptr)return root;
        stk.push(root);
        while(!stk.empty() || root != nullptr){
            root = stk.top();
            stk.pop();
            if(root == nullptr)continue;
            TreeNode* temp = root->right;
            root->right = root->left;   
            root->left = temp;
            stk.emplace(root->left);
            stk.emplace(root->right);  
        }
        return ans;
    }
};

既然明白了这道题的本质是考察遍历，那么这个先序遍历的迭代版就安排上了。

其实这道题说白了是考遍历，任何一种遍历方式都可以处理的。无关先后，因为每一个节点都去把自己的儿子给交换了，就够了，也不会有什么负负得正的情况。

最后官方给的题解：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/invert-binary-tree/solution/fan-zhuan-er-cha-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

他是递归先反转儿子再翻转老子，也说明了哪种遍历都可以玩！