Summary of the tree

Tree is a common data structure used to simulate data sets with tree structure.

Each node in the tree has a value and a list of all the children (another tree, called a subtree).

From a graph point of view, a tree can be regarded as a directed acyclic graph with N nodes and N-1 edges.

Binary tree is a more typical tree structure. As the name implies, a binary tree is a tree structure with at most two subtrees per node, usually called left and right subtrees

Depth-first traversal of trees (DFS)

You need to know the tree constructor before you walk through it

/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; *} * /
Copy the code

Example binary tree diagram:

The order of traversal is as follows:

  • Front traversal (left and right root) : 5, 4, 1, 2, 6, 7, 8
  • Middle order traversal (left root right) : 1 4 2 5 7 6 8
  • After traversal (left and right roots) : 1 2 4 7 8 6 5

The former sequence traversal

A front-order traversal first visits the root node, then the left subtree, and finally the left and right subtree roots

Recursive algorithm: Time complexity O(n) Space complexity O(n)
/* * @param {TreeNode} root * @return {number[]} */
var preorderTraversal = function(root) {
  if(! root)return []
  return [root.val].concat(preorderTraversal(root.left), preorderTraversal(root.right))
};
Copy the code
Iterative algorithm: Time complexity O(n) Space complexity O(n)
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var preorderTraversal = function(root) {
  if(! root)return []
  const stack = []
  const res = []
  stack.push(root)
  while (stack.length) {
    const node = stack.pop()
    res.push(node.val)
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }
  return res
};
Copy the code

In the sequence traversal

Middle-order traversal traverses the left subtree, then visits the root node, and then traverses the right subtree from the left root to the right

Recursive algorithm: Time complexity O(n) Space complexity O(n)
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
  if(! root)return []
  return inorderTraversal(root.left).concat(root.val, inorderTraversal(root.right))
};
Copy the code
Iterative algorithm: Time complexity O(n) Space complexity O(n)
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var inorderTraversal = function(root) {
  if(! root)return []
  const result = [], stack = []
  while(root ! = =null || stack.length > 0) {
    while(root) {
      stack.push(root)
      root = root.left
    }
    const pop = stack.pop()
    result.push(pop.val)
    root = pop.right
  }
  return result
};
Copy the code

After the sequence traversal

Back-order traversal is to traverse the left subtree first, then the right subtree, and finally the left and right roots of the tree

Recursive algorithm: Time complexity O(n) Space complexity O(n)
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var postorderTraversal = function(root) {
  if(! root)return []
  return postorderTraversal(root.left).concat(postorderTraversal(root.right), root.val)
} 
Copy the code
Iterative algorithm: Time complexity O(n) Space complexity O(n)
/ * * *@param {TreeNode} root
 * @return {number[]}* /
var postorderTraversal = function(root) {
  if(! root)return []
  let stack = []
  let res = []
  let prev = null
  while(root ! =null || stack.length) {
    while(root ! =null) {
      stack.push(root)
      root = root.left
    }
    root = stack.pop()
    if (root.right == null || root.right == prev) {
      res.push(root.val)
      prev = root
      root = null
    } else {
      stack.push(root)
      root = root.right
    }
  }
  return res
};
Copy the code
Morris traversal: Time complexity O(n) Space complexity O(1)
/ / morris traversal
var postorderTraversal = function(root) {
  let res = []
  if(! root)return res
  const addPath = (res, node) = > {
    let tmp = []
    while(node ! =null) {
      tmp.push(node.val)
      node = node .right
    }
    for (let i = tmp.length - 1; i >= 0; i--) {
      res.push(tmp[i])
    }
  }
  let p1 = root, p2 = null
  while(p1 ! =null) {
    p2 = p1.left
    if(p2 ! =null) {
      while(p2.right ! =null&& p2.right ! = p1) { p2 = p2.right }if (p2.right == null) {
        p2.right = p1
        p1 = p1.left
        continue
      } else {
        p2.right = null
        addPath(res, p1.left)
      }
    }
    p1 = p1.right
  }
  addPath(res, root)
  return res
};
Copy the code

Pay attention to the point

  1. When a node in the tree is deleted, the deletion process is performed in the same order as the sequential traversal. That is, when you delete a node, you delete its left and right children first, and then delete itself.

skills

  1. It is easier to use the stack to process expressions when traversing backwards:Each time an operator is encountered, the top two elements are popped off the stack, evaluated and returned

Breadth-first traversal of trees (BFS)

Breadth-first search is a traversal or search algorithm that is widely used in data structures such as trees or graphs.

The algorithm starts from a root node and accesses the node itself. It then traverses its neighboring nodes, then its second-level neighbors, third-level neighbors, and so on.

Sequence traversal

Example binary tree diagram:

In the above, the sequence traversal is as follows:

  • Sequence traversal: 5, 46, 1278

Sequence traversal iterative algorithm:

var levelOrder = function(root) {
  let res = []
  if(! root)return res
  let queue = [root] // Queue to root node
  while (queue.length) {
    let currentLength = queue.length
    res.push([]) // Each layer is an array
    for (let i = 0; i < currentLength; i++) {
      let node = queue.shift() // Take out the first node
      res[res.length - 1].push(node.val) // Push the value of this node into the array of the current layer
      if (node.left) queue.push(node.left) // If there are left and right nodes, queue them separately
      if (node.right) queue.push(node.right)
    }
  }
  return res
};
Copy the code

Use recursion to solve tree problems

Recursion is one of the features of trees, using recursion to solve problems within a single node, recursively calling functions to solve problems of its children.

Often, we can solve problems by recursion from the top down or the bottom up

A “top-down” solution

Top-down can be thought of as a kind of sequential traversal. One sentence describes “top down” : the upper level passes the value to the lower level until the last level stops recursion.

Recursive function templates

var top_down = function(root, params) {
  // 1. Special value check (null value returns)
  // 2. Return value update (if required)
  // 3. Get the value of the left child node: left_ans = top_down(root.left, params)
  Right_ans = top_down(root.right, params)
  // 5. Return the final value
}

/** * maximum_depth function: pseudo-code for maximum depth *@params Root Root node *@params The depth depth * /
var maximum_depth = function(root, depth) {
  let answer = 0 // 0. Don't forget to define variables
  Special value check (null value returned) Root node does not return 0 depth
  if(! root)return 0
  // 2. Return value update (if necessary). This assumes that the current node has no left or right nodes
  if (root.left == null && root.right == null) {
    answer = Math.max(answer, depth)
  }
  // 3. Get the value of the left child
  maximum_depth(root.left, depth + 1)
  // 4. Get the value of the right child node
  maximum_depth(root.right, depth + 1)
  // 5. Return final value returns a larger value
  return answer
}
Copy the code

Note the depth function above, which iterates from top to bottom to update the value of answer

“Bottom-up” solutions

Bottom-up can be thought of as a back-order traversal. Bottom up: the upper values depend on the lower values, and finally get two values (the required values of the left and right nodes, such as depth, etc.) to take the maximum.

Recursive function templates

var bottom_up = function(root, params) {
  // 1. Special value check (null value returns)
  // 2. Return value update (if required)
  Bottomt_ans = bottom_up(root.left, params)
  Right_ans = bottom_up(root.right, params)
  // 5. Return the final value
}

/** * maximum_depth function: pseudocode *@params Root Root node */
var maximum_depth = function(root) {
  Special value check (null value returned) Root node does not return 0 depth
  if(! root)return 0
  // 2. Return value update (if required) not required here
  // 3. Get the value of the left child
  let left_depth = maximum_depth(root.left)
  // 4. Get the value of the right child node
  let right_depth = maximum_depth(root.right)
  // 5. Return the final value. Note that + 1 makes the depth + 1
  return Math.max(left_depth, right_depth) + 1
}
Copy the code

When to “top down”? When should you be “bottom-up”?

For the current topic:

  1. Can you identify some parameters that allow the node to solve itself?
  2. Can you use these parameters and the values of the node itself to determine the parameters to be passed to its children?

If so, try solving the problem with top-down recursion

For the current topic:

  1. If you know the answer to its child node, can you calculate the answer to that node?

If you can, try to solve the problem “bottom-up” recursively

Subject to practice

  1. Preorder traversal: 144. Preorder traversal of binary trees
  2. Middle-order traversal: 94. Middle-order traversal of binary trees
  3. Post-order traversal: 145. Post-order traversal of binary trees
  4. Sequence traversal: 102. Sequence traversal of binary trees
  5. Binary tree attributes:
  • 104. Maximum depth of a binary tree
  • 101. Symmetric binary trees
  • 112. Sum of paths