2023.12.15每日一题

2023-12-16 06:42:21

题目来源

力扣每日一题;题序:2415

我的题解

方法一 层序遍历+数值交换

根据层序遍历可以得知是否到达奇数层,若当前层是奇数层就将所有的节点保存到一个数组中,然后对整个数组中的节点进行前后数值交换。

时间复杂度:O(n)。其中 n 表示树中节点的数目。利用广度优先搜索遍历二叉树的每一个节点,需要的时间为 O(n)。
空间复杂度:O(n)。其中 n表示树中节点的数目。利用广度优先搜索遍历二叉树的每一层,每一层最多有?n/2? 个节点,队列中最多存在 ?n/2?个节点,因此需要的空间为 O(n)。

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null))
            return root;
        Queue<TreeNode> queue=new LinkedList<>();
        int level=0;
        queue.offer(root);
        while(!queue.isEmpty()){
            int sz=queue.size();
            List<TreeNode> arr=new ArrayList<>();
            for(int i=0;i<sz;i++){
                TreeNode t=queue.poll();
                if(level%2==1)
                    arr.add(t);
                if(t.left!=null){
                    queue.offer(t.left);
                    queue.offer(t.right);
                }
            }
            if(level%2==1){
                for(int left=0,right=sz-1;left<right;left++,right--){
                    int temp=arr.get(left).val;
                    arr.get(left).val=arr.get(right).val;
                    arr.get(right).val=temp;
                }
            }
            level++;
        }
        return root;
    }
}
方法二 深度优先遍历(参考官方题解)

先进行深度搜索遍历,然后对奇数层进行反转。
具体步骤:

  1. 由于该二叉树是完美二叉树,因此我们可以知道对于根节点来说,它的孩子节点为第一层节点,此时左孩子需要与右孩子需要进行反转;
  2. 当遍历每一层时,由于 root1,root2分别指向该层两个可能需要进行值交换的节点。根据完美二叉树的层次反转规则,即左边排第一的元素与倒数第一元素进行交换,第二个元素与倒数二个元素交换,此时 root1的左孩子与 root2的右孩子可能需要进行交换,root1的右孩子与 root2的左孩子可能需要进行交换。在遍历的同时按照上述规则,将配对的节点进行递归传递到下一层;
  3. 用 isOdd来标记当前层次是否为奇数层,由于偶数层不需要进行交换,当 isOdd 为 true 时,表明当前需要交换,我们直接交换两个节点 root1,root2的值;

时间复杂度:O(n),其中 n 表示树中节点的数目。利用深度优先搜索遍历二叉树的每一个节点,需要的时间为 O(n)。
空间复杂度:O(log?n),其中 n表示树中节点的数目。利用深度优先搜索遍历整个二叉树,由于二叉树为完美二叉树,因此整个树的深度为 log?n,递归深度最大为 log?n,因此需要的空间为 O(log?n)。

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        if(root==null||(root.left==null&&root.right==null))
            return root;
        dfs(root.left,root.right,true);
        return root;
    }
    public void dfs(TreeNode root1,TreeNode root2,boolean isOdd){
        if(root1==null){
            return ;
        }
        // 步骤3
        if(isOdd){
            int  t=root1.val;
            root1.val=root2.val;
            root2.val=t;
        }
        // 步骤2
        dfs(root1.left,root2.right,!isOdd);
        dfs(root1.right,root2.left,!isOdd);
    }
}

哈哈哈哈,刚开始钻牛角尖了,总想着直接交换节点,一时没想到可以交换值。

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

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