Construct a tree data structuretree
That is as follows:
const tree = {
val: "F".left: {
val: "B".left: {
val: "A".left: null
},
right: {
val: "D".left: {
val: "C"
},
right: {
val: "E"}}},right: {
val: "G".right: {
val: "I".left: {
val: "H"}}}};Copy the code
The former sequence traversal
/** * traversal, root -- left -- right *@param {*} root
* @param {*} arr
*/
const preOrder = function (root, arr = []) {
if(! root)return arr;
arr.push(root.val); // Save the root node
preOrder(root.left, arr); // Iterate over the left subtree
preOrder(root.right, arr); // Iterate over the right subtree
return arr;
}
console.log(preOrder(tree)); // ['F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'H']
Copy the code
In the sequence traversal
/** * in order traversal, left - right - root *@param {*} root
* @param {*} arr
*/
const inOrder = function (root, arr = []) {
if(! root)return arr;
inOrder(root.left, arr); // Iterate over the left subtree
arr.push(root.val); // Save the root node in the middle
inOrder(root.right, arr); // Iterate over the left subtree
return arr;
}
console.log(inOrder(tree)); // ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
Copy the code
After the sequence traversal
/** * after traversal, left - right - root *@param {*} root
* @param {*} arr
*/
const postOrder = function (root, arr = []) {
if(! root)return arr;
postOrder(root.left, arr);
postOrder(root.right, arr);
arr.push(root.val);
return arr;
}
console.log(postOrder(tree)); ['A'.'C'.'E'.'D'.'B'.'H'.'I'.'G'.'F']
Copy the code
Note: The above three traversals are depth-first traversals
Breadth-first traversal
/** * breadth-first traversal, returns a one-dimensional array *@param {*} root
*/
var BFS = function (root) {
let queue = []; // first in, first out
let result = [];
queue.push(root);
while (queue.length > 0) {
let node = queue.shift(); // Fetch the header element
result.push(node.val);
if (node.left) {
queue.push(node.left);
}
if(node.right) { queue.push(node.right); }}return result;
};
console.log(BFS(tree)); // ['F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'H']
Copy the code
Sequence traversal
What is sequential traversal? In simple terms, sequential traversal means layering the binary tree and traversing each layer from left to right: at first glance, the traversal order is the same as BFS, and we can use BFS directly to get the result of sequential traversal. However, sequence traversal requires different input results than BFS. Sequential traversal requires us to differentiate each layer, which returns a two-dimensional array. The BFS traversal results in a one-dimensional array that does not distinguish between each layer. Author: nettee
Link: leetcode-cn.com/problems/bi… Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.
/** * order traversal, returns a two-dimensional array containing each layer of elements *@param {*} root
*/
function levelOrder(root) {
let queue = []; //
let result = [];
queue.push(root);
while (queue.length > 0) {
let size = queue.length; // The number of current levels
let levelArr = [];
for (let i = 0; i < size; i++) { // Create a nested loop that processes data at each level
const node = queue.shift();
levelArr.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
result.push(levelArr);
}
return result;
}
console.log(levelOrder(tree));
/ * the results as follows: [[' F '], [' B ', 'G'], [' A ', 'D', 'I'], [' C ', 'E', 'H']] * /
Copy the code