力扣刷题 226.翻转二叉树

题干

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

输入：root = [2,1,3]
输出：[2,3,1]

示例 3：

输入：root = []
输出：[]

解题思路

想要实现翻转，乍一看可能觉得挺难的，但仔细想想就会发现我们只需要交换每个节点的左节点和右节点就可以实现二叉树的翻转。因此，这里面就涉及到了对二叉树每个节点的遍历。我们都知道二叉树有好几种遍历方式，这时我们就体会到之前掌握几种遍历写法的作用了。

我们首先来看如何用前序遍历解题。

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;
    }
};

 1.确定递归函数的参数和返回值

参数就是要传入节点的指针，不需要其他参数了，通常此时定下来主要参数，如果在写递归的逻辑中发现还需要其他参数的时候，随时补充。

返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数，所以就函数的返回类型为TreeNode*。

TreeNode* invertTree(TreeNode* root)

2.确定终止条件

当前节点为空的时候，就返回

if (root == NULL) return root;

3.确定单层递归的逻辑 

先反转当前根节点的左右孩子节点，再翻转左右子树，

// 根(中) 对当前根节点的左右节点交换
swap(root->left,root->right);
//左 翻转左子树
invertTree(root->left);
//右 翻转右子树
invertTree(root->right);

return的返回值返回给了上一级，比如一个递归程序，从第三层返回到第二层；又比如一个普通的子程序，那就返回到主程序中去。主程序中return返回给了操作系统。

这里的return其实不需要，只是因为题干要求返回root节点的指针，所有只在主函数返回时有用

后序遍历

和前序遍历差不多，只要修改交换左右节点的顺序即可

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;
        stack<TreeNode*> st;
        st.push(root);
        while(!st.empty()) {
            TreeNode* node = st.top();              // 中
            st.pop();
            swap(node->left, node->right);
            if(node->right) st.push(node->right);   // 右
            if(node->left) st.push(node->left);     // 左
        }
        return root;
    }
};

统一迭代法（前序遍历）

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root != NULL) st.push(root);
        while (!st.empty()) {
            TreeNode* node = st.top();
            if (node != NULL) {
                st.pop();
                if (node->right) st.push(node->right);  // 右
                if (node->left) st.push(node->left);    // 左
                st.push(node);                          // 中
                st.push(NULL);
            } else {
                st.pop();
                node = st.top();
                st.pop();
                swap(node->left, node->right);          // 节点处理逻辑
            }
        }
        return root;
    }
};

 层序遍历

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
          queue<TreeNode*> que;
          if(root != NULL){
            que.push(root);
          }
          while(!que.empty()){
            // 如何判断每一层的个数
            //记录队列的大小
            int size = que.size();
            // 遍历队列，放入数组
             for(int i = 0; i < size; i++ ){
                //出队列第一个元素放入数组
                TreeNode* node = que.front();
                //将左右节点入队列
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                swap(node->left , node->right);
                //将当前节点弹出
                que.pop();
             } 
          }
    return root;
    }
};