P193 二叉树的 Z 字形遍历

描述#

这个题目说的是，给你一棵二叉树，要求你从根节点到叶子节点一层一层地进行 Z 字形遍历，也就是先从左向右访问一层节点，然后从右向左访问下一层节点。以这样的方式交替去访问二叉树上每一层节点，并且将访问的结果以二维数组的形式返回。

比如说，给你的二叉树是：
1
/ 

2   4
/ 

8  16
它的 Z 字形遍历结果是：
[
[1],
[4, 2],
[8, 16]
]

相关视频：二叉树的层序遍历

代码#

public class AlgoCasts {
  
  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(n)
  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    boolean right2Left = false;

    while (!q.isEmpty()) {
      List<Integer> elem = new ArrayList<>();
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode t = q.poll();
        elem.add(t.val);
        if (t.left != null) q.add(t.left);
        if (t.right != null) q.add(t.right);
      }
      if (right2Left) Collections.reverse(elem);
      result.add(elem);
      right2Left = !right2Left;
    }
    return result;
  }

  // Time: O(n), Space: O(n)
  public List<List<Integer>> zigzagLevelOrderV2(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    boolean right2Left = false;

    while (!q.isEmpty()) {
      List<Integer> elem = new LinkedList<>();
      int size = q.size();
      for (int i = 0; i < size; ++i) {
        TreeNode t = q.poll();
        if (right2Left) elem.add(0, t.val);
        else elem.add(t.val);
        if (t.left != null) q.add(t.left);
        if (t.right != null) q.add(t.right);
      }
      result.add(elem);
      right2Left = !right2Left;
    }
    return result;
  }

}