反转二叉树的奇数层(Leetcode 2415)

题目分析

   本题难度不大，是周赛的第三题，小伙伴们能否在10分钟以内解决本题呢？

广度优先搜索

广搜是比较容易想到的算法，因为广搜是按行来搜索，而本题的要求就是反转特定的行，因此可以搜索出来放在列表中，然后将列表中的元素值反转。

这里要反转列表值，为了快速查找，就不能使用LinkedList，因为元素查找的时间是O(n)的，我们就使用ArrayList保存，但是ArrayList又不能像链表一样删除头元素，因为删除的时间也是O(n)的。题目要求节点是2的14次方，因此不能对每一行再采用O(n)的时间去移动元素或者查找元素。

因此可以用ArrayList模拟链表，只不过不删除元素，用一个下标记录当前的元素位置即可。

算法的**时间复杂度为O(n)，空间复杂度为O(n)**。

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        ArrayList<TreeNode> queue = new ArrayList<>();
        ArrayList<TreeNode> newQueue = new ArrayList<>();
        queue.add(root);
        boolean flag = true;
        while (!queue.isEmpty()) {
            if (queue.get(0).left == null) {
                return root;
            }
            for (TreeNode cur : queue) {
                newQueue.add(cur.left);
                newQueue.add(cur.right);
            }
            if (flag) {
                int len = newQueue.size();
                for (int i = 0; i < len / 2; i++) {
                    int tmp = newQueue.get(i).val;
                    newQueue.get(i).val = newQueue.get(len - 1 - i).val;
                    newQueue.get(len - 1 - i).val = tmp;
                }
            }
            flag = !flag;
            queue = newQueue;
            newQueue = new ArrayList<>();
        }
        return root;
    }
}

深度优先搜索

本题最优雅的方案是利用深搜，对于两个需要交换的节点来说，不妨设为leftNode和rightNode，那么交换过两个值后，应该判断leftNode的left节点和rightNode的right节点是否需要交换，leftNode的right节点和rightNode的left节点是否需要交换。

其实DFS的实现就是这两句话，算法的**时间复杂度为O(n)，空间复杂度为O(log(n))**。

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, true);
        return root;
    }

    private void dfs(TreeNode leftNode, TreeNode rightNode, boolean flag) {
        if (leftNode == null) {
            return;
        }
        if (flag) {
            int tmp = leftNode.val;
            leftNode.val = rightNode.val;
            rightNode.val = tmp;
        }
        dfs(leftNode.left, rightNode.right, !flag);
        dfs(leftNode.right, rightNode.left, !flag);
    }
}

刷题总结

  本题的难度不大，分享这个题目的目的是让小伙伴们学习一下深搜的思想，很神奇~