preface

The first day of February, summarize the recent brush about tree traversal leetcode algorithm problems, I hope to write this article and read the article you have some harvest it. The whole is mainly about the tree traversal, using front-end javascript language. Of course, there is still a lot to understand and summarize about tree manipulation. I’m going to try to understand tree traversal for now. 🧐 🧐

Open dry, first put the map:

1. Trees and binary trees

1.1, trees,

1.1.1 Basic Concepts of trees

Tree is a kind of data structure, it is composed of N (N >=1) finite nodes of a hierarchical relationship set. It’s called a tree because it looks like an upside-down tree, meaning it has roots up and leaves down. It has the following characteristics: each node has zero or more children; Nodes that have no parents are called root nodes; Each non-root node has one and only one parent; In addition to the root, each child can be divided into multiple disjoint subtrees.

There are no trees in javascript, but we can build trees with Object and Array, such as the one shown above:

const tree = {
  val:'a'.children:[
    {
      val:'b'.children:[
        {
          val:'d'.children: []}, {val:'e'.children:[],}]}, {val:'c'.children:[
        {
          val:'f'.children: []}, {val:'g'.children:[],}]}]}Copy the code

Common operations on trees: depth/breadth first traversal, middle first and order second traversal (binary tree)

1.1.2 Tree Depth-first Traversal (DFS)

Search as deep as possible for branches of the tree

1. Access the root node

2. Children of the root node are traversed depth-first one by one

👉 (recursion)

  • Code implementation

(The tree being manipulated here is the one we created with javascript code above)

const dfs = (root) = > {
  console.log(root.val)
  root.children.forEach(dfs)
  // root.children.forEach((child) => {dfs(child)})
  // Traverse each child node of the node, and continue the traverse using DFS recursion on the child node
}
dfs(tree);
Copy the code

Console result

1.1.3 Tree Breadth-first Traversal (BFS)

First access the node closest to the node

The sibling node is traversed first, and the child node is traversed. Adopt queue implementation, add child node when queue.

  • Operation thought

1. Create a queue and add the root node to the queue

2. Get the enemy out of the team and visit

Team up the opposing children one by one

4. Repeat steps 2 and 3 until the queue is empty

👉 (queue)

  • Code operation

(The tree being manipulated here is the one we created with javascript code above)

const bfs = (root) = > {
  Create a queue and add the root node to the queue
  const q = [root]
  Repeat steps 2,3 until the queue is empty
  while (q.length > 0) {
    //2
    const n = q.shift();
    console.log(n.val);
    // 3, Join the opposing children one by one
    n.children.forEach(child= > {
      q.push(child);
    });
  }
}
bfs(tree);
Copy the code

Results printed on the operating table:

1.2. Binary tree

1.2.1 Basic Concepts of binary trees

A binary tree is a tree that can have at most two branches per node. The left branch is called the left subtree, and the right branch is called the right subtree. Create a binary tree in javascript

The code is as follows:

const bt = {
  val:1.left: {val:2.left: {val:4.left:null.right:null
      },
      right: {val:5.left:null.right:null}},right: {val:3.left: {val:6.left:null.right:null
    },
    right: {val:7.left:null.right:null,}}};Copy the code

1.2.2 Sequential traversal of binary trees

The recursive version

1. Access the root node

2. Perform a sequential traversal of the left subtree of the root node

3. Perform a sequential traversal of the right subtree of the root node

✍ ️ 1-2-4-1-2-4-7

Code:

const preorder = (root) = > {
  if(! root) {return }
  console.log(root.val);
  preorder(root.left);
  preorder(root.right)
};
Copy the code

Results:

The recursive version

Stack is used to simulate sequential traversal (root, left, right) recursion

Use the stack data structure

1. Create a stack representing the function call stack, which initially contains the root node

2. Access the value of the root node and use the pop() method

3. First push the right node to the stack, then push the left node to the stack (because the stack is last in, first out), we need to get the left node first access to the right node

4. Loop 2,3 until there is a value in the stack

Code:

const preorder = (root) = > {
  if(! root) {return}
  const stack = [root];
  while(stack.length){
    const n = stack.pop();
    console.log(n.val);// Access this node
    if(n.right) stack.push(n.right);
    if(n.left) stack.push(n.left); }}Copy the code

1.2.3 Middle order traversal of binary tree

The recursive version

1. Middle order traversal is performed on the left subtree of the root node

2. Access the root node

3. Middle order traversal of the right subtree of the root node

✍ ️ 4-2-5-4-2-5-7

Code:

const inorder = (root) = > {
 if(! root){return}
 inorder(root.left);
 console.log(root.val);
 inorder(root.right);
}
Copy the code

The recursive version

Stack is used to simulate intermediate order traversal (left, root, right) recursion

1. Create a stack to represent the function call stack

2, For the middle order traversal, we start with the recursive root.left, so when we use stack emulation, the first step is to throw all the left subtrees on the stack, using the pointer P, starting with root

3. When p has a value, let p= P. ft, while traversing, push it onto the stack

4. Pop up the nearest left node to access it

P = n.right; p = n.right;

6, do it again cycle while (stack. The length | | p) {}

const inorder = (root) = > {
  if(! root) {return; }const stack = [];
  let p = root;
  while (stack.length || p) {
    while(p) {
      stack.push(p);
      p = p.left;
    }
    const n = stack.pop();
    console.log(n.val); p = n.right; }}Copy the code

1.2.4 Back-order traversal of binary trees

The recursive version

1. Post-order traversal of the left subtree of the root node

2. Perform post-order traversal on the right subtree of the root node

3. Access the root node

✍ ️ 4-5-2-4-5-2-1

Code:

const postorder = (root) = > {
  if(! root) {return }
  postorder(root.left)
  postorder(root.right);
  console.log(root.val);
}
Copy the code

The recursive version

Stack is used to simulate post-order traversal (left, right, root) recursion

We know that the sequential traversal is about the root.

So, we can do first order traversal, then use the push operation, and then use the last in, first out of the stack. (Note that we need to change the first order traversal to the root right left, so we need to change it.)

Create a stack that represents the call stack for the function

2, create a stack outputStack implementation inverted stack

Calls the sequential traversal method

const stack = [root];
  while(stack.length){
    const n = stack.pop();
    console.log(n.val);
    if(n.right) stack.push(n.right);
    if(n.left) stack.push(n.left);
  }
Copy the code

3. Change the first traversal root right and left to root left and right

  if(n.left) stack.push(n.left);
  if(n.right) stack.push(n.right);
Copy the code

4. Push the left and right child nodes of the node onto the stack

5. Pop () all the nodes in the outputStack

Code:

const postorder = (root) = > {
  if(! root) {return}
  const stack = [root];
  const  outputStack = [];
  while(stack.length){
    const n = stack.pop();
    //console.log(n.val); // Access this node
    outputStack.push(n); // Change the sequential traversal of the node to push the node onto the stack
    if(n.left) stack.push(n.left);
    if(n.right) stack.push(n.right);
  }
  // Output in reverse order and access
    while(outputStack.length) {
      const n =  outputStack.pop();
      console.log(n.val); }}Copy the code

2. Leetcode

Middle order traversal of binary tree

Title: Middle order traversal of binary trees

  • The recursive version
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
    const res = []
    const rec = (n) = > {
        if(! n) {return}
        rec(n.left);
        res.push(n.val)
        rec(n.right)
    }
    rec(root);
   return res
};
Copy the code
  • Non-recursive (stack)
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
    const res = [];
    // simulate the stack
    const stack = [];
    let p = root;/ / pointer
   while(stack.length || p) {
    while(p) {
        // Add the left subtree to the stack
        stack.push(p);
        p = p.left;// Point to the left node and push it on the stack
    }
    // Pop out the nearest left node (top node element)
    const n = stack.pop();
    res.push(n.val);
    // Access the right node
    p = n.right
   }
   return res
};
Copy the code

Binary tree sequence traversal

Title: Sequence traversal of binary trees

/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var levelOrder = function(root) {
    if(! root) {return[]; }const q = [[root,0]].const res = [];// Access structure
    while(q.length) {
        const [n,l] = q.shift();
        // console.log(n.val,l);
        // When the array res is empty, i.e. empty [], push the node's value inside
        // Other values are placed according to the hierarchy
        if(! res[l]){ res.push([n.val]); }else{
            res[l].push(n.val)
        }
        if(n.left) q.push([n.left,l + 1]);
        if(n.right) q.push([n.right,l + 1]);
        // If the current node has left and right nodes, then the level of traversing the two nodes is increased by one.
        // Because they are one level below the current node
    }
  return res;
};
Copy the code

Maximum depth of a binary tree

Title: Maximum depth of binary trees

🥭 Depth first

/ * * *@param {TreeNode} root
 * @return {number}* /
var maxDepth = function (root) {
  let res = 0;
  / / l presentation layer
  const dfs = (n,l) = > {
    if(! n) {return; }if(! n.left && ! n.right) { res =Math.max(res,l);
    }
    console.log(n,l);
    dfs(n.left,l+1);
    dfs(n.right,l+1);
  };
  dfs(root,1);
  return res
}
Copy the code

111. Minimum depth of a binary tree

Title: Minimum depth of binary trees

🥭 Breadth first

/ * * *@param {TreeNode} root
 * @return {number}* /
// Minimum depth of binary tree -- width first
var minDepth = function(root) {
    if(! root) {return 0}
    const q = [[root,1]].while(q.length) {
      const [n,l] = q.shift();
      if(! n.left && ! n.right) {return l;
      }
      if (n.left) q.push([n.left,l + 1]);
      if (n.right) q.push([n.right,l + 1]); }};Copy the code

112. Sum of paths

Title: Minimum depth of binary trees

/ * * *@param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}* /
var hasPathSum = function(root, targetSum) {
 if(! root)return false;
 let res = false;// flag to determine whether the targetSum is met
 const dfs = (n,s) = > {
     if(! n.left && ! n.right && s === targetSum) { res =true;
     }
     if (n.left) dfs(n.left, s + n.left.val)
     if (n.right) dfs(n.right,s + n.right.val);
 };
 dfs(root,root.val);
 return res;
};
Copy the code

3, front-end related

Iterate over all the values of JSON

The object.keys () method returns an array of the given Object’s own enumerable properties

Depth-first traversal

const json = {
  a: {b: {c:1}},d: [1.2]}const dfs = (n) = > {
  console.log(n); //{ a: { b: { c: 1 } }, d: [ 1, 2 ] }
  console.log(Object.keys(n)) //[ 'a', 'd' ]
  Object.keys(n).forEach(k= > {
    dfs(n[k])
  })
}
dfs(json)
Copy the code

Results:


{ b: { c: 1 } }
[ 'b' ]
{ c: 1 }
[ 'c' ]
1
[]
[ 1, 2 ]
[ '0', '1' ]
1
[]
2
[]

Copy the code

conclusion

Well, that’s enough tree traversal for today. As a summary, the title of Leetcode is not as detailed as it says, you can refer to the previous tree depth/breadth first traversal, and binary tree middle first order traversal.

😁 February, good luck!

😳 humble code word, for praise

💌 Fried chicken thank you

🙈 cartridge