【二叉树, DFS】反转二叉树的奇数层【力扣第 311 场周赛】

题目

6182. 反转二叉树的奇数层

---

给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。

• 例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。

反转后，返回树的根节点。

完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。

节点的 层数 等于该节点到根节点之间的边数。

示例 1：

输入：root = [2,3,5,8,13,21,34]
输出：[2,5,3,8,13,21,34]
解释：
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 ，反转后为 5、3 。

示例 2：

输入：root = [7,13,11]
输出：[7,11,13]
解释： 
在第 1 层的节点分别是 13、11 ，反转后为 11、13 。

示例 3：

输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
解释：奇数层由非零值组成。
在第 1 层的节点分别是 1、2 ，反转后为 2、1 。
在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。

提示：

• 树中的节点数目在范围 [1, 2^14] 内
• 0 <= Node.val <= 10^5
• root 是一棵 完美 二叉树

解题

方法一：层序遍历

思路

层序遍历二叉树并把节点值存入一个二维哈希表(helper)中，然后把哈希表中的奇数层反转，再利用这个哈希表重建二叉树。

代码

class Solution {
    List<List<Integer>> helper = new ArrayList<>();
    
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root, 0);
        for (int i = 0; i < helper.size(); ++i) {
            if ((i & 1) != 0) Collections.reverse(helper.get(i));
        }
        build(root, 0);
        return root;
    }
    
    void dfs(TreeNode node, int level) {
        if (node == null) return;
        if (helper.size() == level) helper.add(new ArrayList<>());
        helper.get(level).add(node.val);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }
    
    void build(TreeNode node, int level) {
        if (node == null) return;
        var list = helper.get(level);
        node.val = list.get(0);
        list.remove(0);
        build(node.left, level + 1);
        build(node.right, level + 1);
    }
}

方法二：DFS

思路

由于题目保证了该二叉树是个满二叉树，所以可以同时镜像地深搜二叉树的左右端，具体来说：
左端前序遍历，右端后序遍历，当层数为奇数层时就把左右节点值交换。

参考：https://www.bilibili.com/video/BV1jG4y1B77r?t=282.6

代码

class Solution {
    public TreeNode reverseOddLevels(TreeNode root) {
        mirroredDfs(root.left, root.right, 1);
        return root;
    }
    
    void mirroredDfs(TreeNode left, TreeNode right, int level) {
        if (left == null) return;
        if ((level & 1) != 0) {
            int tmp = left.val;
            left.val = right.val;
            right.val = tmp;
        }
        mirroredDfs(left.left, right.right, level + 1);
        mirroredDfs(left.right, right.left, level + 1);
    }
}