了解如何计算二叉树的深度

Question

我将通过基础CS原理的速成课程来学习职业生涯杯指南，并停留在计算二叉树的最小/最大深度的示例上。由于这是我遇到的几乎每个示例都存在的相同问题，我认为我会在此处发布问题。

这些说明将实现一种方法，该方法将检查树是否平衡。为此，您需要比较最小深度和最大深度，并确保它们之间的差异不大于1。此原理一目了然。第15行上的方法旨在做到这一点。

但是，我不了解每个辅助方法（maxDepth和minDepth）的return语句中发生了什么。如何从root.left或得出一个数字root.right？是否Math.max功能简单地假设一个1或一个0是有一个值/空节点，或者，由于没有正在值指定（只是Node对象），并Math.max(maxDepth(root.left), maxDepth(root.right)本身等于0，从而通过增加的返回值1，直到两个节点都为空？

如果是这样，则一般过程用于计算树的最小/最大深度：

minDepth =根是否有子代？是= minDepth = 1，否= minDepth = 0（如果有根）

maxDepth =在两个分支之间循环，直到找到离根最远的叶子。保持计数器去确定叶子。

1   public static int maxDepth(TreeNode root) {
2       if (root == null) {
3       return 0;
4       }
5       return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
6   }
7
8   public static int minDepth(TreeNode root) {
9       if (root == null) {
10          return 0;
11      }
12      return 1 + Math.min(minDepth(root.left), minDepth(root.right));
13  }
14
15  public static boolean isBalanced(TreeNode root){
16      return (maxDepth(root) - minDepth(root) <= 1);
17  }

Answer 1

maxDepth(root.left)返回左子树的最大深度。
maxDepth(root.right)返回右侧子树的最大深度。
这两个的最大值是最大子树深度。
为根节点加1，可以得到树的最大深度。

假设这是树：

            A
         B      C
       D   E   F   G
     H
   I

只需查看它，您就可以看到最大深度为5（由路径ABDHI形成），最小深度为3（由多个路径形成，例如ACG）。

现在，最大深度为1（对于根A）+两个子树的最大深度。
根为B的第一个子树的最大深度为4（BDHI）。根为C的第二个子树的最大深度为2（CF）。
max（4,2）= 4
因此，整个树的最大深度为1 + max（4,2）= 5。

如果我们在示例树中使用字母表示根于这些节点的子树，则得到：

maxDepth(A) = 1 + max(maxDepth(B) , maxDepth(C)) =
              1 + max(1 + max(maxDepth(D) , maxDepth(E)), 1 + max(maxDepth(F) , maxDepth(G)) =
              1 + max(1 + max(1+max(maxDepth(H),0) , 1+max(0,0)), 1 + max(1+max(0,0) , 1+max(0,0)) =
              1 + max(1 + max(1+max(1+max(maxDepth(I),0),0) , 1), 1 + 1) =
              1 + max(1 + max(1+max(1+max(1+max(0,0),0),0) , 1), 1 + 1) =
              1 + max(1 + max(1+max(1+max(1,0),0) , 1), 2) =
              1 + max(1 + max(1+max(2,0) , 1), 2) =
              1 + max(1 + max(3 , 1), 2) =
              1 + max(4, 2) =
              1 + 4 =
              5

同样，要计算最小深度，您需要计算两个（左右）子树的最小深度，取两个子树中的最小值，并为根添加1。