前端刷题路-Day13|刷题打卡

我心飞翔 分类:javascript

掘金团队号上线,助你 Offer 临门! 点击 查看详情

二叉树的最小深度(题号111)

题目

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明:叶子节点是指没有子节点的节点。

示例 1:

img

输入:root = [3,9,20,null,null,15,7]
输出:2
 

示例 2:

输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
 

提示:

  • 树中节点数的范围在 [0, 105]
  • -1000 <= Node.val <= 1000

链接

leetcode-cn.com/problems/mi…

解释

这题写出了遍历,但是没写出递归,其实递归也不难,可能想得太复杂了

自己的答案(递归)

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
};
 

没啥可说的,在对应的地方加上对应的代码即可。

更好的方法(递归)

const minDepth = (root) => {
    if (root == null) {            // 递归到null节点,返回高度0
        return 0;
    }
    if (root.left && root.right) { // 左右子树都存在,当前节点的高度1+左右子树递归结果的较小值
        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 {                       // 左右子树都不存在,光是当前节点的高度1
        return 1;
    }
};
 

一看代码就觉得挺简单的,没啥可说的

更好的方法(递归)

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;
    }
};
 

和上一种方法换汤不管药

括号生成(题号22)

题目

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
 

示例 2:

输入:n = 1
输出:["()"]
 

提示:

1 <= n <= 8

链接

leetcode-cn.com/problems/ge…

解释

用到了一个新知识——剪枝,就是在添加元素时判断是否满足条件,如果不满足条件,就不进行下一步操作,避免错误的形成。

查阅了一些相关答案,发现基本上都是这种方法,有用动态规划做这个的,但是代码比较复杂,难以理解。

自己的答案

更好的答案(DFS+剪枝)

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
};
 

这一题是我想的太复杂了,总感觉有更好的解法,其实没有。

我本来的想法是通过规律来给出多种情况的组合条件,之后在递归中排列组合,可这其中的规律实在比较复杂,好像有点涉及到动态规划了,最后还是不了了之。

👆的这种解法其实是比较简单的,基本原理是一种往字符串中进行填充,但是填充时需要注意是不是满足条件,如果满足条件再进行填充,不满足就算了,这里的不满足就是剪枝了。

条件也比较简单,给定lL为左括号剩余数量,rL为右括号剩余数量。首先判断结束条件,当二者都为0时,判断为填充结束,向listpush字符串。

之后如果左括号还有剩余,那就往字符串中添加一个左括号。如果右括号的数量大于左括号,那就往字符串中添加一个右括号。只要满足这两个条件就可以得出正确的字符串。

逻辑比较简单,难的是想到这种方法。

PS:想查看往期文章和题目可以点击下面的链接:

这里是按照日期分类的👇

前端刷题路-目录(日期分类)

经过有些朋友的提醒,感觉也应该按照题型分类
这里是按照题型分类的👇

前端刷题路-目录(题型分类)

有兴趣的也可以看看我的个人主页👇

Here is RZ

回复

我来回复
  • 暂无回复内容