111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例： :::info 给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2. :::

思路

1. DFS

记录一个最小值，同时在递归过程中记录深度，然后当 DFS 到该节点为叶子节点时，更新min。
当整棵树遍历完毕后，返回min即可。

  1. var minDepth = function(root) {
  2.     let min = Infinity;
  3.     const dfs = (root, depth) => {
  4.         if (!root) return;
  5.         if (!root.left && !root.right) {
  6.             min = Math.min(min, depth);
  7.             return;
  8.         }
  9.         if (root.left) {
  10.             dfs(root.left, depth+1);
  11.         }
  12.         if (root.right) {
  13.             dfs(root.right, depth+1);
  14.         }
  15.     }
  16.     dfs(root, 1)
  17.     return min === Infinity ? 0 : min
  18. };

2. BFS

采用 BFS，从低到高逐个层级去遍历树，当发现某一层的某个节点为叶子节点时，直接返回当前层级即可。

  1. var minDepth = function(root) {
  2.     let depth = 0;
  3.     if (!root) return depth;
  4.     const queue = [root];
  5.     while (queue.length) {
  6.         const len = queue.length;
  7.         depth++;
  8.         for (let i = 0; i < len; i++) {
  9.             const node = queue.shift();
  10.             if (!node.left && !node.right) {
  11.                 return depth;
  12.             }
  13.             if (node.left) {
  14.                 queue.push(node.left);
  15.             }
  16.             if (node.right) {
  17.                 queue.push(node.right);
  18.             }
  19.         }
  20.     }
  21. };

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：

  1. 给定二叉树 [3,9,20,null,null,15,7]，
  2.     3
  3.    / \
  4.   9  20
  5.     /  \
  6.    15   7
  7. 返回它的最大深度 3 。

思路

具体的思路与上述的 二叉树的最小深度 相似，这里就不赘述了。

1. DFS

  1. let maxDepth = function (root) {
  2.   let max = 0
  3.   let helper = (node, depth) => {
  4.     if (!node) return
  5.     max = Math.max(max, depth)
  6.     if (node.left) {
  7.       helper(node.left, depth + 1)
  8.     }
  9.     if (node.right) {
  10.       helper(node.right, depth + 1)
  11.     }
  12.   }
  13.   helper(root, 1)
  14.   return max
  15. }

2. BFS

  1. let maxDepth = function (root) {
  2.   if (!root) return 0
  3.   let max = 0
  4.   let queue = [root]
  6.   while (queue.length) {
  7.     max += 1
  8.     let len = queue.length
  9.     while (len--) {
  10.       let node = queue.shift()
  11.       if (node.left) {
  12.         queue.push(node.left)
  13.       }
  14.       if (node.right) {
  15.         queue.push(node.right)
  16.       }
  17.     }
  18.   }
  20.   return max
  21. }

解法三

  1. let maxDepth = function(root) {
  2.   if (!root) return 0
  3.   return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
  4. };