侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 470 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【递归】二叉树的锯齿形层序遍历

GabrielxD
2022-06-10 / 0 评论 / 0 点赞 / 31 阅读 / 298 字 / 正在检测是否收录...

题目

103. 二叉树的锯齿形层序遍历


给你二叉树的根节点 root ,返回其节点值的 锯齿形层序遍历 。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

示例 1:

image-20220610001336771

输入:root = [3,9,20,null,null,15,7]
输出:[[3],[20,9],[15,7]]

示例 2:

输入:root = [1]
输出:[[1]]

示例 3:

输入:root = []
输出:[]

提示:

  • 树中节点数目在范围 [0, 2000]
  • -100 <= Node.val <= 100

解题

方法一:递归

思路

使用层序遍历,记录当前遍历到的层数

  • 当前层为偶数时正常插入值到结果集合。
  • 当前层为偶数时,逆序插入值。

代码

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        zigzagLevelOrder(root, ans, 0);
        return ans;
    }

    public void zigzagLevelOrder(TreeNode root, List<List<Integer>> store, int level) {
        if (root == null) {
            return;
        }

        if (store.size() == level) {
            store.add(new ArrayList<Integer>());
        }

        if ((level & 1) == 1){
            store.get(level).add(0, root.val);
        } else {
            store.get(level).add(root.val);
        }

        zigzagLevelOrder(root.left, store, level + 1);
        zigzagLevelOrder(root.right, store, level + 1);
    }
}
0

评论区