103. Binary Tree Zigzag Level Order Traversal

解法一

思路

We can use the iteration method in 102. We use a LinkedList to store ndoes on each level. We observe that the odd level traverse from left to right, and the right level traverse from right to left. So for even level, we always poll the head on LinkedList, and add their children from left to right to the end of the LinkedList. For odd level, we always remove the last element in the LinkedList, and add their from right to left to the head of the LinkedList.

代码

Class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<>();
        if (root  == null) {
            return levels;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        list.add(root);
        int level = 0;
        while(!list.isEmpty()) {
            int length = list.size();
            levels.add(new ArrayList<Integer>());
            for (int i = 0; i < length; i++) {
                // Even level
                if (level % 2 == 0) {
                    TreeNode node = list.poll();
                    levels.get(level).add(node.val);
                    if (node.left != null) {
                        list.add(node.left);
                    }
                    if (node.right != null) {
                        list.add(node.right);
                    }
                }
                // Odd level
                else {
                    TreeNode node = list.removeLast();
                    levels.get(level).add(node.val);
                    if (node.right != null) {
                        list.addFirst(node.right);
                    }
                    if (node.left != null) {
                        list.addFirst(node.left);
                    }
                }
            }
            level++;
        }
        return levels;
    }
}

复杂度分析

• 时间复杂度
  O(N)
• 空间复杂度
  O(N)

解法二

思路

代码

复杂度分析

• 时间复杂度
  • 最好情况
  • 最坏情况
  • 平均情况
• 空间复杂度

Takeaway

本作品采用《CC 协议》，转载必须注明作者和本文链接