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

Question

我正在通过 Career Cup 指南作为基本 CS 原则的速成类(class)，并坚持计算二叉树的最小/最大深度的示例。由于这是我几乎每个示例都遇到的相同问题，我想我会在这里发布一个问题。

这些说明是为了实现一种方法，该方法将检查树是否平衡。为此，您需要比较最小深度和最大深度，并确保它们的差值不大于 1。这个原理非常简单。第 15 行的方法就是为了做到这一点。

但是，我不明白每个辅助方法(maxDepth 和minDepth)的返回语句中发生了什么。一个数字是如何从 root.left 或 root.right 派生出来的？ Math.max 函数是否简单地假定 1 或 0 是否存在值/空节点，或者因为没有值指定(只是 Node 对象)，Math.max(maxDepth(root.left), maxDepth(root.right) 本身是否等于 0 , 从而将返回值递增 1 直到两个节点都为空？

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

minDepth = 根节点有 child 吗？ yes = minDepth = 1, no = 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(由路径 A-B-D-H-I 形成)，最小深度为 3(由多个路径形成，例如 A-C-G)。

现在，最大深度为 1(对于根 A)+ 两个子树的最大深度。
根为 B 的第一棵子树的最大深度为 4 (B-D-H-I)。第二个子树，其根为 C，最大深度为 2 (C-F)。
最大值(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。