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

题目

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

---

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

示例 1：

输入：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);
    }
}