-
Notifications
You must be signed in to change notification settings - Fork 0
/
103-binary-tree-zigzag-level-order-traversal.js
108 lines (100 loc) · 2.49 KB
/
103-binary-tree-zigzag-level-order-traversal.js
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
const zigzagLevelOrder = function (root) {
if (root == null) return [];
const row = [root];
const res = [];
bfs(row, res);
for (let i = 0; i < res.length; i++) {
res[i] = i % 2 === 0 ? res[i] : res[i].reverse();
}
return res;
};
function bfs(row, res) {
if (row.length === 0) return;
let tmp = [];
let next = [];
for (let i = 0; i < row.length; i++) {
tmp.push(row[i].val);
if (row[i].left) {
next.push(row[i].left);
}
if (row[i].right) {
next.push(row[i].right);
}
}
if (tmp.length) {
res.push(tmp);
}
bfs(next, res);
}
// another
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
const zigzagLevelOrder = function (root) {
if (!root) return [];
const queue = [root];
const zigzag = [];
let numLevels = 1;
while (queue.length > 0) {
const width = queue.length;
const levelTraversal = [];
for (let i = 0; i < width; i++) {
const currentNode = queue.shift();
if (currentNode.right) queue.push(currentNode.right);
if (currentNode.left) queue.push(currentNode.left);
numLevels % 2 === 0
? levelTraversal.push(currentNode.val)
: levelTraversal.unshift(currentNode.val);
}
zigzag.push(levelTraversal);
numLevels++;
}
return zigzag;
};
// another
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[][]}
*/
const zigzagLevelOrder = function (root) {
const res = [];
dfs(root, res, 0);
return res;
function dfs(node, res, level) {
if (node == null) return;
if (res.length <= level) res.push([]);
const tmp = res[level];
if (level % 2 === 0) tmp.push(node.val);
else tmp.unshift(node.val);
dfs(node.left, res, level + 1);
dfs(node.right, res, level + 1);
}
};