226.翻转二叉树

力扣链接https://leetcode.cn/problems/invert-binary-tree/description/

题目描述：

给你一棵二叉树的根节点 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 = []
输出：[]

 思路分析：

翻转二叉树，其实就把每一个节点的左右孩子交换一下就可以了。注意，是每一个节点的左右子节点。这就可以用到前面所将的二叉树递归遍历和层序遍历。下面分别使用前序递归，后序递归和层序遍历来实现。

前序递归实现：

先回顾一下递归三部曲：

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

2. 确定递归终止条件

3. 确定单层递归的逻辑操作有哪些

首先，对于函数参数，由于要遍历二叉树，所以要有一个TreeNode*指针来接收根节点，由于不需要对元素提取或其他操作，所以不再需要其他参数。其次，由于题目要求返回翻转后的根节点，所以返回值类型为TreeNode*。

TreeNode* invertTree(TreeNode* root)

第二，递归何时终止？当遇到要遍历的节点的指针为nullptr时，遍历终止。这里的root不仅表示根节点，还可以表示遍历过程中左右子树对应的根节点。

if (root == NULL) return root;

第三，单层递归要做哪些操作？前序遍历首先就要交换左右子节点，然后递归调用本函数分别对左右子树进行同样的操作，然后返回root。

swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;

整体代码如下： 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //递归前序遍历第一步：确定递归函数参数以及返回值
    TreeNode* invertTree(TreeNode* root) {
        //第二步：确定递归终止条件。当前节点指针为空，递归结束
        if(root == nullptr) return root;
        //第三步：确认单层递归的逻辑
        //前序遍历
        swap(root->left, root->right);  //中，交换
        invertTree(root->left);         //左，递归
        invertTree(root->right);        //右，递归
        return root;
    }
};

后序递归实现：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //递归后序遍历第一步：确定递归函数参数以及返回值
    TreeNode* invertTree(TreeNode* root) {
        //第二步：确定递归终止条件。当前节点指针为空，递归结束
        if(root == nullptr) 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->left);         // 注意 这里依然要遍历左孩子，因为中间节点已经翻转了
        return root;
    }
};

层序遍历实现：

class Solution {
public:
    //层序遍历需要借助队列queue
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode *> que;
        if(root != nullptr) 
            que.push(root);
        else
            return root;
        while(!que.empty())
        {
            int size = que.size();
            for(int i =0; i<size; i++)
            {
                TreeNode * node = que.front();
                //注意，先交换，再入队左右子节点。否则会先遍历右节点                
                swap(node->left, node->right);
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);    
                que.pop();
            }
        }
        
        return root;

    }
};

本人在写代码的时候，曾经多给交换前加了个条件，即

//注意，先交换，再入队左右子节点。否则会先遍历右节点
if(node->left!=nullptr && node->right != nullptr)
     swap(node->left, node->right);

想的是当前节点的左右节点均存在时才进行交换，但是程序未通过：

错误原因是，程序要实现的代码时即使左右子节点未能同时存在，也能完成交换（和nullptr）交换。如下图所示：

 所以这个加上的前提条件是不正确的，因此需要删除。