103. Binary Tree Zigzag Level Order Traversal

难度: Medium

题目描述

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

 

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

 

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

解题思路

代码实现

解决方案

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        if (root == null) {
            return new ArrayList<>();
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        dfs(root, 0, map);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < map.size(); i++) {
            if(i%2==1){
                res.add(map.get(i).reversed());
            }else{
                 res.add(map.get(i));
            }
            
        }

        return res;
    }

    private void dfs(TreeNode root, int depth, Map<Integer, List<Integer>> map) {
        if (root == null) {
            return;
        }
        List<Integer> data = map.get(depth);
        if (data == null) {
            data = new ArrayList<>();
            map.put(depth, data);
        }
        data.add(root.val);

        dfs(root.left, depth + 1, map);
        dfs(root.right, depth + 1, map);

    }
}