【每日一题】反转二叉树的奇数层
Tag
【深度优先搜索】【广度优先搜索】【二叉树】【2023-12-15】
题目来源
题目解读
反转二叉树奇数层的节点。
解题思路
对于二叉树中的节点反转,我们只需要交换节点的值。通常有广度优先搜索和深度优先搜索两种解决方法。
方法一:广度优先搜索
思路
按层遍历二叉树,将奇数层的节点都记录下来,如果当前的层是奇数层,就交换节点数组中的节点。
算法
在具体实现中,通过维护一个 bool 变量 isOdd 来记录当前层是否是奇数层。初始化 isOdd = false
,因为广搜从根节点开始,这一层是 0 层当做偶数层。每遍历完一层之后更新 isOdd = !isOdd
,下方实现中使用的是异或运算来更改 isOdd
。
/**
* 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* reverseOddLevels(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
bool isOdd = false;
while (!q.empty()) {
int sz = q.size();
vector<TreeNode*> arr;
for (int i = 0; i < sz; ++i) {
TreeNode* node = q.front();
q.pop();
if (isOdd) {
arr.push_back(node);
}
if (node->left) { // 完美二叉树,有左子树一定也有右子树
q.push(node->left);
q.push(node->right);
}
}
if (isOdd) {
for (int l = 0, r = sz - 1; l < r; ++l, --r) {
swap(arr[l]->val, arr[r]->val);
}
}
isOdd ^= true;
}
return root;
}
};
复杂度分析
时间复杂度: O ( n ) O(n) O(n), n n n 是二叉树中节点个数,每个节点都要被遍历一次。
空间复杂度: O ( n ) O(n) O(n),用数组记录二叉树的每一层的节点数,某一层最多有 ? n 2 ? \lceil{\frac{n}{2}}\rceil ?2n?? 个节点,因此空间复杂度为 O ( n ) O(n) O(n)。
方法二:深度优先搜索
思路
核心依然是交换值,通过递归左右子树实现。
算法
/**
* 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:
void dfs(TreeNode* root1, TreeNode* root2, bool isOdd) {
if (root1 == nullptr) {
return;
}
if (isOdd) {
swap(root1->val, root2->val);
}
dfs(root1->left, root2->right, !isOdd);
dfs(root1->right, root2->left, !isOdd);
}
TreeNode* reverseOddLevels(TreeNode* root) {
dfs(root->left, root->right, true);
return root;
}
};
复杂度分析
时间复杂度: O ( n ) O(n) O(n), n n n 是二叉树中节点个数,每个节点都要被遍历一次。
空间复杂度: O ( l o g n ) O(logn) O(logn)。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。
如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。
最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!