律师做网站,wordpress移动模块位置,网站推广的资源合作推广,英文外贸网站设计文章目录 Tag题目来源题目解读解题思路方法一#xff1a;广度优先搜索方法二#xff1a;深度优先搜索 写在最后 Tag
【深度优先搜索】【广度优先搜索】【二叉树】【2023-12-15】 题目来源
2415. 反转二叉树的奇数层 题目解读
反转二叉树奇数层的节点。 解题思路
对于二叉… 文章目录 Tag题目来源题目解读解题思路方法一广度优先搜索方法二深度优先搜索 写在最后 Tag
【深度优先搜索】【广度优先搜索】【二叉树】【2023-12-15】 题目来源
2415. 反转二叉树的奇数层 题目解读
反转二叉树奇数层的节点。 解题思路
对于二叉树中的节点反转我们只需要交换节点的值。通常有广度优先搜索和深度优先搜索两种解决方法。
方法一广度优先搜索
思路
按层遍历二叉树将奇数层的节点都记录下来如果当前的层是奇数层就交换节点数组中的节点。
算法
在具体实现中通过维护一个 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) {queueTreeNode* q;q.push(root);bool isOdd false;while (!q.empty()) {int sz q.size();vectorTreeNode* 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)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
