Nuggets team number online, help you Offer rimmon! Click to see details

Minimum depth of binary tree (Question No. 111)

The title

Given a binary tree, find its minimum depth.

Minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node.

Note: A leaf node is a node with no child nodes.

Example 1:

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

Example 2:

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

Tip:

  • The number of nodes in the tree ranges from[0, 105] 内
  • -1000 <= Node.val <= 1000

link

Leetcode-cn.com/problems/mi…

explain

It writes the traversal, but it doesn’t write the recursion, and the recursion isn’t that hard, maybe it’s too complicated

Your own answer (recursion)

var minDepth = function (root) { if (! root) return 0 var arr = [root] var level = 0 while (arr.length > 0) { var aL = arr.length for (let i = 0; i < aL; i++) { var node = arr.shift() if (! node.left && ! node.right) { arr.length = 0 level++ break } if (i === aL - 1) level++ node.left && arr.push(node.left) node.right && arr.push(node.right) } } return level };Copy the code

There is nothing to say, just add the corresponding code in the corresponding place.

A better way (recursion)

Const minDepth = (root) => {if (root == null) {return 0; } if (root.left && root.right) {// both subtrees exist, Return 1+ math.min (minDepth(root.left), minDepth(root.right)); } else if (root.left) {return 1 + minDepth(root.left); } else if (root.right) {return 1 + minDepth(root.right); } else {// there is no left or right subtree, light is the height of the current node 1 return 1; }};Copy the code

Look at the code, it’s pretty simple, nothing to say

A better way (recursion)

const minDepth = (root) => { if (root == null) { return 0; } const left = minDepth(root.left); const right = minDepth(root.right); if (left > 0 && right > 0) { return 1 + Math.min(left, right); } else if (left > 0) { return 1 + left; } else if (right > 0) { return 1 + right; } else { return 1; }};Copy the code

And the previous method to change the soup regardless of the medicine

Generation of parentheses (Question number 22)

The title

The number N represents the logarithm that generates parentheses. Design a function that generates all possible and valid parentheses combinations.

Example 1:

Input: n = 3 output: [" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"]Copy the code

Example 2:

Input: n = 1 Output: ["()"]Copy the code

Tip:

1 <= n <= 8

link

Leetcode-cn.com/problems/ge…

explain

Using a new knowledge – pruning, is to determine whether the condition is met when adding elements, if not meet the condition, do not proceed to the next step, to avoid the formation of mistakes.

Look up some related answers, found that basically is this method, useful dynamic programming to do this, but the code is more complex, difficult to understand.

Your own answer

There is no

Better answer (DFS+ pruning)

var generateParenthesis = function(n) {
  var list = []
  getStr(n, n, '')
  function getStr(lL, rL, str) {
    if (lL === 0 && rL === 0) {
      return list.push(str)
    }
    if (lL > 0) {
      getStr(lL - 1, rL, `${str}(`)
    }
    if (rL > lL) {
      getStr(lL, rL - 1, `${str})`)
    }
  }
  return list
};
Copy the code

I think this problem is too complicated, always feel there is a better solution, but there is not.

My idea was to use the rules to give combinations of situations, and then to arrange them in a recursive way, but the rules were so complicated that it seemed to involve dynamic programming, so I just didn’t do it.

👆 this solution is actually relatively simple, the basic principle is a way to fill the string, but the filling need to pay attention to whether to meet the condition, if the condition is met to fill, do not meet the calculate, here is not satisfied is pruning.

The condition is also simple, given that lL is the number of left open parentheses and rL is the number of left close parentheses. First, determine the end condition. When both are 0, determine that the padding is complete and push the string into the list.

After that, if there’s still an open parenthesis left, add an open parenthesis to the string. Add a closing parenthesis to the string if the number of closing parentheses is greater than the number of opening parentheses. As long as these two conditions are met, you get the right string.

The logic is simple, the hard part is coming up with this method.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ