网站建设捌金手指下拉十四,html中秋节网页制作代码,潍坊制作网站,太原做网站个人226.翻转二叉树
力扣链接https://leetcode.cn/problems/invert-binary-tree/description/
题目描述#xff1a;
给你一棵二叉树的根节点 root #xff0c;翻转这棵二叉树#xff0c;并返回其根节点。
示例 1#xff1a; 输入#xff1a;root [4,2,7,1,3,6,9]
输出
给你一棵二叉树的根节点 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) {queueTreeNode * que;if(root ! nullptr) que.push(root);elsereturn root;while(!que.empty()){int size que.size();for(int i 0; isize; 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交换。如下图所示 所以这个加上的前提条件是不正确的因此需要删除。
