LeetCode: 103. Binary Tree Zigzag Level Order Traversal

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

103. Binary Tree Zigzag Level Order Traversal

LeetCode - 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,null,null,15,7],

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

思路分析

一刷
二刷
三刷

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Runtime: 1 ms, faster than 75.19% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
 *
 * Memory Usage: 41.5 MB, less than 5.77% of Java online submissions for Binary Tree Zigzag Level Order Traversal.
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2020-01-24 21:12
 */
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    if (Objects.isNull(root)) {
        return Collections.emptyList();
    }
    List<List<Integer>> result = new ArrayList<>();
    List<TreeNode> level = new ArrayList<>();
    level.add(root);
    boolean isReverse = false;
    while (!level.isEmpty()) {
        List<TreeNode> temp = new ArrayList<>();
        List<Integer> values = new ArrayList<>(level.size());
        for (TreeNode node : level) {
            if (isReverse) {
                values.add(0, node.val);
            } else {
                values.add(node.val);
            }
            if (Objects.nonNull(node.left)) {
                temp.add(node.left);
            }
            if (Objects.nonNull(node.right)) {
                temp.add(node.right);
            }
        }
        result.add(values);
        level = temp;
        isReverse = !isReverse;
    }
    return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-25 11:27
 */
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  if (root == null) {
    return Collections.emptyList();
  }
  List<List<Integer>> result = new ArrayList<>();
  Queue<TreeNode> queue = new LinkedList<>();
  queue.offer(root);
  boolean reversed = false;
  while (!queue.isEmpty()) {
    int size = queue.size();
    List<Integer> list = new LinkedList<>();
    for (int i = 0; i < size; i++) {
      TreeNode node = queue.poll();
      if (reversed) {
        list.add(0, node.val);
      } else {
        list.add(node.val);
      }
      if (node.left != null) {
        queue.offer(node.left);
      }
      if (node.right != null) {
        queue.offer(node.right);
      }
    }
    result.add(list);
    reversed = !reversed;
  }
  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-09-19 22:15:19
 */
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  if (root == null) {
    return Collections.emptyList();
  }
  List<List<Integer>> result = new LinkedList<>();
  List<TreeNode> stack = new LinkedList<>();
  stack.add(root);
  boolean flag = true;
  while (!stack.isEmpty()) {
    int size = stack.size();
    List<Integer> nums = new LinkedList<>();
    for (int i = 0; i < size; i++) {
      TreeNode node = stack.removeFirst();
      if (flag) {
        nums.addLast(node.val);
      } else {
        nums.addFirst(node.val);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
      if (node.right != null) {
        stack.add(node.right);
      }
    }
    flag = !flag;
    result.add(nums);
  }
  return result;
}