算法练习第15天|226.翻转二叉树

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://层序遍历需要借助队列queueTreeNode* invertTree(TreeNode* root) {queue<TreeNode *> que;if(root != nullptr) que.push(root);elsereturn 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）交换。如下图所示：

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