本文主要是介绍算法练习第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)交换。如下图所示:
所以这个加上的前提条件是不正确的,因此需要删除。
这篇关于算法练习第15天|226.翻转二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!