LeetCode: Binary Tree Level Order Traversal Solution

Implementation

1/**
2 * Definition for a binary tree node.
3 * function TreeNode(val, left, right) {
4 *     this.val = (val===undefined ? 0 : val)
5 *     this.left = (left===undefined ? null : left)
6 *     this.right = (right===undefined ? null : right)
7 * }
8 */
9/**
10 * @param {TreeNode} root
11 * @return {number[][]}
12 */
13// tree preorder traversal
14var levelOrder = function (root) {
15  const res = []
16
17  const recursion = (node, level = 0) => {
18    if (!node) return
19
20    if (!res[level]) res[level] = []
21
22    res[level].push(node.val)
23
24    recursion(node.left, level + 1)
25    recursion(node.right, level + 1)
26  }
27
28  recursion(root, 0)
29
30  return res
31}
32
33// bfs
34var levelOrder = function (root) {
35  const queue = []
36  const res = []
37
38  if (!root) return res
39
40  queue.unshift(root)
41  while (queue.length) {
42    const currentQueueLength = queue.length
43    const subList = []
44    for (let i = 0; i < currentQueueLength; i++) {
45      queue[0].left && queue.push(queue[0].left)
46      queue[0].right && queue.push(queue[0].right)
47      subList.push(queue.shift().val)
48    }
49    res.push(subList)
50  }
51
52  return res
53}

References

Original problem