103. Binary Tree Zigzag Level Order Traversal

Version #1 Deque
二刷
写了一个非常容易出错的bug，在levelResult.add()的时候应该add node value而不是node本身，这个非常需要注意
11.37 %
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        Deque<TreeNode> que = new ArrayDeque<>();
        int level = 0;
        que.offerFirst(root);
        TreeNode curr;
        int size;
        while (!que.isEmpty()) {
            size = que.size();
            //operation in the current level
            List<Integer> levelResult = new ArrayList<>();
            while (size-- > 0) {
                if (level % 2 == 0) {
                    curr = que.pollFirst();
                    levelResult.add(curr.val);
                    if (curr.left != null) que.offerLast(curr.left);
                    if (curr.right != null) que.offerLast(curr.right);
                } else {
                    curr = que.pollLast();
                    levelResult.add(curr.val);
                    if (curr.right != null) que.offerFirst(curr.right);
                    if (curr.left != null) que.offerFirst(curr.left);
                }
            }
            result.add(levelResult);
            level++;
        }
        return result;
    }
}


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (root == null) return result;
        Deque<TreeNode> que = new ArrayDeque<TreeNode>();
        que.addFirst(root);
        int level = 0;
        int size = 0;
        TreeNode curr = null;
        while (!que.isEmpty()) {
            size = que.size();
            level++;
            List<Integer> subResult = new ArrayList<Integer>();
            for (int i = 0; i < size; i++) {
                if (level % 2 == 1) {
                    curr = que.pollFirst();
                    subResult.add(curr.val);
                    if (curr.left != null) {
                        que.addLast(curr.left);
                    }
                    if (curr.right != null) {
                        que.addLast(curr.right);
                    }
                } else {
                   curr = que.pollLast();
                   subResult.add(curr.val);
                   if (curr.right != null) {
                       que.addFirst(curr.right);
                   }
                   if (curr.left != null) {
                       que.addFirst(curr.left);
                   }
                }
            }
            result.add(subResult);
        }
        return result;
    }
}
Version #2 DFS
LinkedList, ArrayList好像性能上没有什么区别
但是理论上还是应该用LinkedList
90.84 %

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        int level = 1;
        zigzagDfs(root, level, result);
        return result;
    }
    private static void zigzagDfs(TreeNode root, int level, List<List<Integer>> result) {
        if (root == null) return;
        if (result.size() < level) result.add(new LinkedList<Integer>());
        List<Integer> curr = result.get(level - 1);
        if (level % 2 == 1) {
            curr.add(root.val);
        } else {
            curr.add(0, root.val);
        }
        zigzagDfs(root.left, level + 1, result);
        zigzagDfs(root.right, level + 1, result);
    }
}

三刷

Version #3

Time O(n)

Space O(n)

Runtime: 1 ms, faster than 76.84% of Java online submissions for Binary Tree Zigzag Level Order Traversal.

Memory Usage: 38.9 MB, less than 86.75% of Java online submissions for Binary Tree Zigzag Level Order Traversal.

没有用前面Version#1的Deque方法

回归最基本的顺序level order traversal

when it's the even layer, always append the element to the last

when it's the odd layer, always insert the element to the first position

class Solution {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {

        if (root == null) {

            return new ArrayList<>();

        }

        List<List<Integer>> res = new ArrayList<>();

        int level = 0;

        Queue<TreeNode> que = new LinkedList<>();

        que.offer(root);

        while (!que.isEmpty()) {

            int size = que.size();

            List<Integer> layer = new LinkedList<>();

            while (size-- > 0) {

                TreeNode curr = que.poll();

                if (level % 2 == 0) {

                    layer.add(curr.val);

                } else {

                    layer.add(0, curr.val);

                }

                if (curr.left != null) {

                    que.offer(curr.left);

                }

                if (curr.right != null) {

                    que.offer(curr.right);

                }

            }

            res.add(layer);

            level++;

        }

        return res;

    }

}