Leetcode 103 二叉树的锯齿形层序遍历 // 洛七的摸鱼池塘

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

解答

本题的难度是 Medium.

也是写了很抽象的代码, 都不知道自己脑子那几天在想什么? 太怪了.

代码如下:

class Solution {
    private HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>();
    private int maxDepth = -1;
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        levelOrder(root, 0);
        for (int i = 0; i <= maxDepth; i++) {
            ArrayList<Integer> list = hashMap.get(i);
            if (i%2 == 1){
                Collections.reverse(list);
            }
            result.add(list);
        }
        return result;

    }

    private void levelOrder(TreeNode node, int depth){
        if(node == null) {return;}
        if(maxDepth < depth) {maxDepth = depth;}
        ArrayList<Integer> list = hashMap.getOrDefault(depth, new ArrayList<Integer>());

        list.add(node.val);
        hashMap.put(depth, list);
        levelOrder(node.left, depth+1);
        levelOrder(node.right, depth+1);
    }
}

用时 1ms, 击败 71.92% 的提交.

改了一下, 本质还是层序遍历, 然后奇数层或者偶数层(主要看你定义根节点是第0层还是第1层)的 List reverse 一下就行.

class Solution {
    List<List<Integer>> lists = new ArrayList<>();
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ceng(0, root);
        List<Integer> list;
        for (int i = 0; i < lists.size(); i++) {
            list = lists.get(i);
            if (i%2 == 1){
                Collections.reverse(list);
            }
        }
        return lists;
    }
    private void ceng(int cengIndex, TreeNode node){
        if(node == null ){return ;}
        if(lists.size() < (1+cengIndex)){
            lists.add(new ArrayList<>());
        }
        lists.get(cengIndex).add(node.val);
        ceng(cengIndex+1, node.left);
        ceng(cengIndex+1, node.right);
    }
}

改完之后时间开销为 0ms, 击败 100% 的提交.