LeetCode——2415. 反转二叉树的奇数层

通过万岁！！！

• 题目：给你一个完全二叉树，然后将其奇数层进行反转。
• 思路：这个题他都说了是奇数层了，那基本就是层序遍历了。但是存在两个问题，一个是如何判断奇数层，另外一个是如何进行交换。首先是第一个问题，如何判断是奇数层。这个问题比较简单，由于我们每次往数组中添加的都是左右两个节点的元素。因此，如果队列中的元素个数是2的n次方，并且n是一个奇数，则表示奇数层。然后就是反转了，这里需要借助一个list集合，我没有找到队列有反转的方法，如果有的话，空间复杂度可以小一点。值得注意的是，在最后一层元素出队的时候，也会遇到奇数层的情况，所以我们需要记录层数，层数必须是一直增加的。
• 思路：层序遍历，队列。

java代码

class Solution {
   
    public TreeNode reverseOddLevels(TreeNode root) {
   
        if (root == null || root.left == null) {
   
            return root;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int r;
        int l;
        double level = 0;
        while (queue.size() != 0) {
   
            TreeNode remove = queue.remove();
            if (remove.left != null) {
   
                queue.add(remove.left);
            }
            if (remove.right != null) {
   
                queue.add(remove.right);
            }
            r = queue.size() - 1;
            l = 0;
            double newLevel = Math.log(r + 1) / Math.log(2);
            if (newLevel < level) {
   
                continue;
            } else {
   
                level = newLevel;
            }
            // 如果是奇数层，则就需要进行交换了
            if (newLevel % 2 == 1) {
   
                List<TreeNode> transList = new ArrayList<>(r);
                for (TreeNode treeNode : queue) {
   
                    transList.add(treeNode);
                }
                while (r > l) {
   
                    int temp = transList.get(r).val;
                    transList.get(r).val = transList.get(l).val;
                    transList.get(l).val = temp;
                    l++;
                    r--;
                }
            }
        }
        return root;
    }
}

• 总结：其实这个问题比较简单的。