103 二叉树的锯齿形层次遍历

# 103 二叉树的锯齿形层次遍历

# 题目链接

# 难度：中等

# 思路分析：

广度或者深度，存的顺序要一致和取的顺序按照遍历的方向

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 想

# 一

# 想

# 再

# 看

# 答

# 案

# 代码：

广度优先：核心是左侧一直在前面右侧一直在后面取的时候按照遍历顺序从前或者从后取

var zigzagLevelOrder = function(root) {
  if (root == null) return [];
  var arr = [root];
  var res = [];
  var go = true;
  while (arr.length > 0) {
    var n = arr.length;
    var now = [];
    if (go) {
      while (n > 0) {
        // 从左侧往右
        var node = arr.shift();
        now.push(node.val);
        // 下一轮是 从右往左
        // 从左往右循环一定要用push unshift右侧的值会在前面
        if (node.left != null) arr.push(node.left); // 左侧在前面
        if (node.right != null) arr.push(node.right); // 右侧在后面
        n--;
      }
      res.push(now); // 添加当前层级
    } else {
      while (n > 0) {
        // 从右往左 先取后面的
        var node = arr.pop();
        now.push(node.val);
        // 下一轮是从左往右
        // TODO: 从右往左一定要用unshift 用push左边的树的子节点可能会在后面
        if (node.right != null) arr.unshift(node.right); // 右侧在后面
        if (node.left != null) arr.unshift(node.left); // 左侧在前面
        n--;
      }
      res.push(now);
    }
    go = !go; // 更改方向
  }
  return res;
};

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

# 鼓励我一下：

觉得还不错的话，给我的项目点个star吧

# 点个Star支持我一下~