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

2023-12-15 13:54:38

?🔥博客主页:?A_SHOWY
🎥系列专栏力扣刷题总结录?数据结构??云计算??数字图像处理??力扣每日一题_

2415. 反转二叉树的奇数层icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree/

今天终于碰到了一个mid题目,不用经受hard题目的折磨了,是一个树的反转问题,我们可以从深度优先遍历和广度优先遍历两种方法进行求解。深度的话,奇数层就翻转,然后对应的部分再进行递归就可以。广度的话代码复杂一些但是思路简单,不用递归,将奇数层数的存到数组中,后续判定是奇数层就反转。一层一层解决。

方法一: 深度优先遍历?

  • 在遍历每一层的时候?,root1和root2分别指向这一层可能需要交换的两个结点,根据完美二叉树的反转规则,即左边排第一的元素与倒数第一元素进行交换,第二个元素与倒数二个元素交换,此时root1的左孩子和root2的右孩子换,root1的右孩子和root2的左孩子交换,在遍历的同时按照上述规则,将配对的节点进行递归传递到下一层;
  • isOdd来表示是否为奇数,偶数层不需要交换,在递归的时候急着进行一个isOdd取逆的操作。
  • 注意当左子树为空的时候,直接返回。

总体代码?

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
    dfs(root-> left,root ->right,true);
        return root;
    }
    void dfs(TreeNode* root1,TreeNode* root2,bool isOdd){
        if(root1 == NULL) return;
        //判定是不是奇数
        if(isOdd) {
            swap(root1->val,root2->val);
        }
        dfs(root1 -> left,root2 -> right,!isOdd);
        dfs(root1 -> right,root2 -> left, !isOdd);
    }
};

方法二: 广度优先遍历?

  • 在遍历的同时,对每一层进行标记,如果当前该层为奇数层,则将该层中的节点用数组保存起来,然后将该层所有节点的值进行反转即可。
  • 判断有左子树的时候,就继续存下一层
  • 反转swap的时候使用了简单的双指针,一定要记住->val
  • 记住最后再取反
    isOdd ^= true;

总体代码:?

class Solution {
public:
    TreeNode* reverseOddLevels(TreeNode* root) {
        queue<TreeNode *> q;
        //根结点导进去
        q.emplace(root);
        bool isOdd = false;
        while(!q.empty()){
         int sz = q.size();
        vector<TreeNode *> reverse;
        for(int i =0; i< sz; i++){
            TreeNode* node = q.front();
            q.pop();
            if(isOdd){
                reverse.push_back(node);
            }
            //如果有左子节点导入队列,为了下一层
            if(node -> left){
                q.emplace(node-> left);
                q.emplace(node-> right);
            }
        }
            //奇数就翻转,双指针
            if(isOdd){
              for(int l =0,r = sz -1;l < r;l++,r--){
                  swap(reverse[l] -> val,reverse[r]-> val);
              }
            }
             isOdd ^= true;//取反;
        }
          return root;
    }
    
};

?

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