[code non-stop – algorithm] binary tree hierarchy traversal

The title

Give you a binary tree, and ask you to return the values of the nodes it traverses in order. (that is, access all nodes layer by layer, from left to right).

Example:

Binary tree: {val: 3, left: {val: 9}, right: {val: 20, left: {val: 15}, right: {val: 7}}

Returns its sequence traversal result:

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

Breadth-first traversal and depth-first traversal

Depth-first traversal is actually similar to the pre-order traversal of a tree, while breadth-first traversal is similar to the hierarchical traversal of a tree.

The depth-first traversal of the tree above is the order ABDEGCF

Method: Start at the root node of the tree and draw a line along the edge of the tree. The first node you encounter accesses it.

The breadth-first traversal of the tree above is the order ABCDEFG

Method: Start at the root node of the tree and access the node from top to bottom, left to right.

Antithesis thought

The sequential traversal of a binary tree is the breadth-first traversal of a binary tree. Breadth-first traversal is looking down one level at a time, so you can imagine a binary tree data structure, going up and down, finding the data at the current level, grouping the data at the current level into an array, and then going down and sorting, The key here is that you always have to decide which tree you’re looking at and where to go next. Each node has a pointer to the next node, and you to the next level traversal of nodes is your current traverse the nodes have the number of Pointers (left and right), so, as long as we traverse to the current node, and judge him “Pointers”, so just push to the next to traverse in the array, Throw away the current layer after traversing it, because you can’t traverse it again the next time you traverse the tree. Well, the ones traversed first have to be thrown away first. This is FIFO. The queue is just FIFO.

Code implementation

/** * 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) { const res = []; // Define an array to hold the result if (! root) return res; Const queue = []; const queue = []; // Define a queue queue.push(root); Const subRes = []; // const subRes = []; // const subRes = []; // const subRes = []; Const Len = Queue. Length; // For (let I = 0; i < len; I++) {const node = Queue. Shift (); const node = Queue. Shift (); Subres.push (node.val); subres.push (node.val); If (node.left) queue.push(node.left); If (node.right) queue.push(node.right); if (node.right) queue.push(node.right); } res.push(subRes); } return res;} return res; };