LeetCode 二叉树最小/大深度

二叉树最小深度

二叉树最大深度

思考

容易想到的是通过 DFS 遍历携带深度信息，记录深度最大值或最小值。

var minDepth = function (root) {
  if (root === null) {
    return 0;
  }

  // 记录最小深度（根节点到最近的叶子节点的距离）
  let minDepthValue = Infinity;

  // 记录当前遍历到的节点深度
  let currentDepth = 0;

  const traverse = function (root) {
    if (root === null) {
      return;
    }

    // 前序位置进入节点时增加当前深度
    currentDepth++;

    // 如果当前节点是叶子节点，更新最小深度
    if (root.left === null && root.right === null) {
      minDepthValue = Math.min(minDepthValue, currentDepth);
    }

    traverse(root.left);
    traverse(root.right);

    // 后序位置离开节点时减少当前深度
    currentDepth--;
  };

  // 从根节点开始 DFS 遍历
  traverse(root);
  return minDepthValue;
};

也可以想到为了避免全局定义深度变量，可以把深度放到递归的参数中，下面是最大深度的解法：

const dig = (root, length) => {
  if (root == null) return length;
  return Math.max(dig(root.left, length + 1), dig(root.right, length + 1));
};
var maxDepth = function (root) {
  if (root === null) return 0;

  // 由于退出条件是在叶子节点的左或右的null节点
  // 因此深度会被多加1, 所以开始计数从0开始，可以满足条件
  return dig(root, 0);
};

但是当用这种思路解决最小深度时，就会遇到问题。

因为是求最小深度，因此递归到叶子节点拿到的高度，是一个无效值，它可能被一个更小的值取代。

但是子树如果为 null,不能参与计算，因此下面的逻辑当遍历到叶子节点时，仍然递归进入空节点，导致空的子树被算作 1 的长度 返回错误的结果。

接下来，如果只有左子树，或者右子树，是不会进入退出逻辑的，这会导致递归无法被正确的处理，当只有其中一个子树的时候，要正确处理子树的返回值。

const dig = (root, length) => {
  // 避免递归进入空节点
  // + if(!node.left && !node.right) return deep;
  // - if (root == null) return length;

  // 当只有一个子树的时候，给空的子树一个默认值 Infinity
  // 因为有值的子树，一定会进入推出逻辑返回一个当前深度值

  // + let left = Infinity,right=Infinity;
  // + if(node.left)  left =  dfs(node.left, deep + 1);
  // + if(node.right) right = dfs(node.right, deep + 1);
  // - return Math.min(dig(root.left, length + 1), dig(root.right, length + 1));

  return Math.min(left, right);
};
var maxDepth = function (root) {
  if (root === null) return 0;
  // 从 1 开始计数
  // + return dig(root, 1);
  // - return dig(root, 0);
};

优化

观察解题思路，是通过传递一个深度参数进行递归，也就是说这是从根节点开始计数，如果从叶子节点开始计数，就可以避免参数的传递。

最大深度计算：

var maxDepth = function (root) {
    if (root === null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};

最小深度计算：

var minDepth = function (root) {
  if (root === null) return 0;

  let left = minDepth(root.left);
  let right = minDepth(root.right);

  // 解决左右子树其中一个为空的情况
  if (left === 0) return right + 1;
  if (right === 0) return left + 1;

  return Math.min(left, right) + 1;
};

对于最小深度，还可以考虑用 BFS 层序遍历来优化，因为最小深度，是要找到第一个叶子节点所在的深度，而不需要像 DFS 那样，每一个分支走到头才知道哪一条路径是最短的。

var minDepth = function (root) {
  let deep = 0;
  if (root === null) return deep;
  let queue = [root];
  let len;
  while ((len = queue.length)) {
    deep++;
    const q = queue.concat([]);
    queue = [];
    while (len--) {
      const node = q.pop();
      if (node.left === null && node.right === null) return deep;

      if (node.right) queue.push(node.right);
      if (node.left) queue.push(node.left);
    }
  }
  return deep;
};

打赏