侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-18 / 0 评论 / 0 点赞 / 254 阅读 / 748 字
温馨提示:
本文最后更新于 2022-09-19,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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

思路

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

image-20220918160438516

参考: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);
    }
}
0

评论区