【每日一题】反转二叉树的奇数层

2023-12-15 14:36:18

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) {
        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)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

文章来源:https://blog.csdn.net/weixin_54383080/article/details/135015806
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。