[111. The minimum depth of binary trees]

The title

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Note: Leaf nodes are nodes that have no child nodes.

Example 1:

Input: root = [3,9,20,null,null,15,7] output: 2

Example 2:

Input: root = [2, null, 3, null, 4, null, 5, null, 6] output: 5

Analysis of the

1. The shortest distance from the root node to the cotyledons

2. Cotyledons are nodes without left and right child nodes

3. Return the shortest distance

solution

1. The recursion

2. The iteration

Solution a:recursive

Train of thought1.The termination condition is that there are no children2.When you recurse, you carry the height of each layer, h+ after each recursion1
3.Note that recursion is performed only when there are child nodes, otherwise a null pointer exception */ will be reportedvar minDepth = function (root) {
  // The initial minimum knowledge is infinite
  let res = Infinity;
  Return 0 for a feature case when the tree is empty
  if(! root)return 0;

  // Carry height when recursing
  function minDep(root, h) {
    // Assign the minimum value to res when reaching the cotyledon
    if(! root.left && ! root.right) { res =Math.min(res, h);
      return;
    }
    // The recursion height increases by one
    h = h + 1;
    // Do not recurse until there are children, otherwise null pointer exceptions will be reported
    root.left && minDep(root.left, h);
    root.right && minDep(root.right, h);
  }

  minDep(root, 1);

  return res;
};

/* Complexity time O(n) space O(n) */
Copy the code

Solution two: iteration

Train of thought1.Iteration is similar to recursion, except that stack is used to simulate recursion2.Stack push {root: root,h: 1} to record the value and height of each node3.Start updating res */ when leaf nodes are satisfiedvar minDepth = function (root) {
  // The initial minimum knowledge is infinite
  let res = Infinity;
  Return 0 for a feature case when the tree is empty
  if(! root)return 0;
  const stack = [];
// Push {root: root, h: 1} in the stack to record the value and height of each node
  stack.push({ root, h: 1 });

  while (stack.length) {
    const { root, h } = stack.pop();
    // Start updating res when leaf nodes are satisfied
    if(! root.left && ! root.right) { res =Math.min(res, h);
    }

    root.left && stack.push({ root: root.left, h: h + 1 });
    root.right && stack.push({ root: root.right, h: h + 1 });
  }

  return res;
};
/* Complexity time O(n) space O(n) */

Copy the code

conclusion

Today this problem is mainly to practice the use of recursion to find the minimum depth and how to use stack simulation recursion to find the minimum depth

You can have a look at a column I share (front-end algorithm) where there are more topics about the algorithm to share, I hope to help you, I will try to keep updated every night, if you like the trouble to help me to like, thank you very much

If you’re interested in “TS” check out my column (TypeScript common knowledge) and thank you for supporting it

The purpose of this article is to study, discuss and share the experience in the process of learning algorithm. Some of the materials in this article are from the network. If there is infringement, please contact to delete, [email protected]