Binary Tree Zigzag Level Order Traversal

描述

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

For example:

Given binary tree {3,9,20,#,#,15,7},

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

return its zigzag level order traversal as:

  1. [
  2.   [3],
  3.   [20,9],
  4.   [15,7]
  5. ]

分析

广度优先遍历，用一个bool记录是从左到右还是从右到左，每一层结束就翻转一下。

递归版

  1. // Binary Tree Zigzag Level Order Traversal
  2. // 递归版，时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List> zigzagLevelOrder(TreeNode root) {
  5.         List> result = new ArrayList<>();
  6.         traverse(root, 1, result, true);
  7.         return result;
  8.     }
  10.     private static void traverse(TreeNode root, int level, List> result,
  11.                                  boolean left_to_right) {
  12.         if (root == null) return;
  14.         if (level > result.size())
  15.             result.add(new ArrayList<>());
  17.         if (left_to_right)
  18.             result.get(level-1).add(root.val);
  19.         else
  20.             result.get(level-1).add(0, root.val);
  22.         traverse(root.left, level+1, result, !left_to_right);
  23.         traverse(root.right, level+1, result, !left_to_right);
  24.     }
  25. }

迭代版

  1. // Binary Tree Zigzag Level Order Traversal
  2. // 广度优先遍历，用一个bool记录是从左到右还是从右到左，每一层结束就翻转一下。
  3. // 迭代版，时间复杂度O(n)，空间复杂度O(n)
  4. public class Solution {
  5.     public List> zigzagLevelOrder(TreeNode root) {
  6.         List> result = new ArrayList<>();
  7.         Queue current = new LinkedList<>();
  8.         Queue next = new LinkedList<>();
  9.         boolean left_to_right = true;
  11.         if(root == null) {
  12.             return result;
  13.         } else {
  14.             current.offer(root);
  15.         }
  17.         while (!current.isEmpty()) {
  18.             ArrayList level = new ArrayList<>(); // elments in one level
  19.             while (!current.isEmpty()) {
  20.                 TreeNode node = current.poll();
  21.                 level.add(node.val);
  22.                 if (node.left != null) next.offer(node.left);
  23.                 if (node.right != null) next.offer(node.right);
  24.             }
  25.             if (!left_to_right) Collections.reverse(level);
  26.             result.add(level);
  27.             left_to_right = !left_to_right;
  28.             // swap
  29.             Queue tmp = current;
  30.             current = next;
  31.             next = tmp;
  32.         }
  33.         return result;
  34.     }
  35. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/binary-tree/traversal/binary-tree-zigzag-level-order-traversal.html