The title

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right). Link: leetcode-cn.com/problems/bi…

Their thinking

  • The sequence traversal order is breadth-first traversal
  • Note that the hierarchy of the current node needs to be recorded during traversal so that it can be added to different arrays

The steps to solve the problem

  • Breadth-first traversal of a binary tree
  • The hierarchy of each node is recorded during the traversal and added to different arrays

code

/** * 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[][]} */ var levelOrder = function(root) { if (! root) return [] let q = [[root,0]] let res = [] while(q.length) { const [n,l] = q.shift() console.log(n.val,l) res[l] ? res[l].push(n.val) : res[l] = [n.val] n.left && q.push([n.left,l+1]) n.right && q.push([n.right,l+1]) } return res };Copy the code

Another way to do it

It can be found in the body of the breadth-first traversal while loop that each loop is a cycle process of constantly removing the old node from the queue and adding its child nodes to the queue. If we can ensure that every iteration can remove all the old nodes from the queue and add their child nodes (all nodes of the next level) to the queue, We can make sure that the body of the while comes in with all the nodes of the same level, so we can add the nodes of the same level to an array to fit into the larger array.

var levelOrder = function(root) { if (! root) return [] let q = [root] let res = [] while(q.length) { let len = q.length res.push([]) while(len--){ const n = q.shift() res[res.length-1].push(n.val) n.left && q.push(n.left) n.right && q.push(n.right) } } return res };Copy the code

Time complexity and space complexity

Because we’re traversing the tree, the time is O(n), which defines q for the number of nodes in the tree, so the space is O(n).