BFS && DFS | yuijam

102. Binary Tree Level Order Traversal

function TreeNode(val) {
  this.val = val;
  this.left = this.right = null;
}

这个题比较符合人们考虑方式的做法是用BFS一层层来遍历二叉树。

BFS是从根节点出发，一层一层的扩散出去，每次都取当前层的儿子节点，一直遍历下去。

一开始我写成这样：

// 执行用时 : 76 ms , 在所有 JavaScript 提交中击败了 23.67% 的用户
// 内存消耗 : 34.9 MB , 在所有 JavaScript 提交中击败了 21.39% 的用户
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  let res = []
  let level = []
  level.push(root)
  let children = function (parents) {
    let c = []
    for (let i = 0; i < parents.length; i++) {
      if (parents[i] !== undefined && parents[i] !== null) {
        c.push(parents[i].left)
        c.push(parents[i].right)
      }
    }
    return c
  }
  while (level.length > 0) {
    let vals = []
    for (let i = 0; i < level.length; i++) {
      if (level[i]) {
        vals.push(level[i].val)
      }
    }
    if (vals.length > 0) {
      res.push(vals)
    }
    level = children(level)
  }
  return res
};

通过是通过了，真是这个用时让我有点困惑，这还能怎么快？然后我想到了之前把for ... of ...改成for (let i = 0 .....) 这种形式居然提高了速度，于是我试着把里面的push换成了索引的方式来存值，类似这样：

let children = function (parents) {
  let c = []
  let j = 0
  for (let i = 0; i < parents.length; i++) {
    if (parents[i] !== undefined && parents[i] !== null) {
      c[j++] = parents[i].left
      c[j++] = parents[i].right
    }
  }
  return c
}

结果 …… 真的变快了。😂

执行用时 :64 ms, 在所有 JavaScript 提交中击败了85.56%的用户

内存消耗 :36.1 MB, 在所有 JavaScript 提交中击败了5.47%的

最后我把所有的push都改了后：

执行用时 :60 ms, 在所有 JavaScript 提交中击败了94.25%的用户

内存消耗 :35.9 MB, 在所有 JavaScript 提交中击败了5.47%的用户炫耀一下:

最终代码：

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  let children = function (parents) {
    let c = []
    let j = 0
    for (let i = 0; i < parents.length; i++) {
      if (parents[i] !== undefined && parents[i] !== null) {
        c[j++] = parents[i].left
        c[j++] = parents[i].right
      }
    }
    return c
  }

  let getVals = function (level) {
    let vals = []
    let j = 0
    for (let i = 0; i < level.length; i++) {
      if (level[i]) {
        vals[j++] = level[i].val
      }
    }
    return vals
  }
  let res = []
  let level = []
  level[0] = root
  let j = 0
  while (level.length > 0) {
    let vals = getVals(level)
    if (vals.length > 0) {
      res[j++] = vals
    }
    level = children(level)
  }
  return res
};

这个题也可以用DFS来做，这样递归写起来很简洁，看着也比较舒服，复杂度O(N)

DFS的做法是一直在一条分支上走到底，然后再往上回溯

// 64 ms 85.56%
var levelOrder = function(root) {
  if (!root) return []
  let res = []
  let level = 0
  let DFS = function (parent, level) {
    if (!parent) return
    if (res.length < level + 1) {
      res.push([])
    }
    res[level].push(parent.val)
    DFS (parent.left, level + 1)
    DFS (parent.right, level + 1)
  }
  DFS (root, level)
  return res
};

102 二叉树的最大深度

DFS和BFS都可以做。用BFS的话，因为是一层层的从上往下扫荡，一直扫描到最底层即可。用DFS的话，用递归写起来很简洁。

// 72 ms 74.29%
// 37.3 mb 36.36%
var maxDepth = function (root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
};

111 二叉树的最小深度

同样BFS和DFS都可以做。同样用DFS写起来代码少点，但是处理最小深度和最大深度稍微不太一样，不能直接把上面的代码改成min，当只有左子树和只有右子树的时候就会有问题。

// 72 ms 77.20%
// 37.2mb 69.67%
var minDepth = function(root) {
  if (!root) return 0;
  let res = null
  let goDeep = function (parent, level) {
    if (res && level > res) return; // 比最小大就可以不继续走下去了
    if (!parent.left && !parent.right) {
      if (!res || level < res) {
        res = level
        return
      }
    }

    if (parent.left) {
      goDeep(parent.left, level + 1)
    }

    if (parent.right) {
      goDeep(parent.right, level + 1)
    }
  }

  goDeep(root, 1)
  return res
};

看了老师的代码，发现还能更简洁：

// 72 ms 77.20%
// 37.1mb 83.29%
var minDepth = function(root) {
  if (!root) return 0;
  let left = minDepth(root.left)
  let right = minDepth(root.right)
  
  return (left === 0 || right === 0 ? left + right + 1 : 1 + Math.min(left, right))
};

这个代码巧妙的处理了那种左右只有一边存在的情况，这种情况就不用min的方式，而用left + right + 1来返回，优雅。

22 括号生成

这个题暴力做法是有的，把所有排列组合都生成出来，然后一个个校验，校验括号的合法性之前用堆栈也做过了，所以，做肯定是可以做的，我一开始是这么想的。老师最后说的也是在这种方式上改进，当发现当前情况肯定是错误组合的情况下，停止递归下去。这种情况包括：

在准备生成右括号的时候，当前字符串中左括号的数量一定要大于右括号的数量。最简单的说，一开始就放一个右括号肯定是不对的。
括号要配对，那就意味着左右括号的数量要一样，等于给定的n

/**
 * @param {number} n
 * @return {string[]}
 */
// 64ms 81.72%
// 35mb 58.89%
var generateParenthesis = function(n) {
  let res = []
  let i = 0
  let gen = function(left, right, substr) {
    if (left === n && right === n) {
      res[i++] = substr
      return
    }
    
    if (left < n) {
      gen(left + 1, right, substr + '(')
    }

    if (left > right && right < n) {
      gen(left, right + 1, substr + ')')
    }
  }

  gen(0, 0, '')
  return res
};

这个代码看着真舒服，仔细琢磨这个过程，感觉递归真是神奇。