了解如何计算二叉树的深度 [英] Understanding how to calculate the depth of a Binary Tree

问题描述

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

I am going through the Career Cup guide as a crash course through basic CS principals and stuck on the example which calculates the minimum/maximum depth of a Binary Tree. Since this is the same problem I'm having with almost every example I thought I'd post a question here.

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

The instructions are to implement a method that will check to see if a tree is balanced. In order to do this, you need to compare the minimum depth with the maximum depth, and ensure their difference is no greater than 1. This principal is as straightforward as it gets. The method on line 15 is intended to do just that.

但是，我不理解每个辅助方法(maxDepth和minDepth)的return语句中发生了什么.如何从root.left或root.right派生数字? Math.max函数只是假设1或0是否存在值/空节点，还是因为没有指定值(只是Node对象)，所以Math.max(maxDepth(root.left), maxDepth(root.right)本身等于0，从而将返回值增加1，直到两个节点都为空?

However, I do not understand what is going on in the return statements of each helper method (maxDepth and minDepth). How is a number being derived from either root.left or root.right? Does the Math.max function simply assume a 1 or a 0 is there a value/null node, or, since there is no value being specified (just the Node object), does Math.max(maxDepth(root.left), maxDepth(root.right) itself equal 0, thus incrementing the return value by 1 until both nodes are null?

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

If so is this the general process used to calculate the min/max depth of a tree:

minDepth =根是否有子代?是= minDepth = 1，否= minDepth = 0(如果有根)

minDepth = does the root have any children? yes = minDepth = 1, no = minDepth = 0 (if there is a root)

maxDepth =遍历两个分支，直到找到离根最远的叶子.保持计数器去确定叶子.

maxDepth = cycle through both branches until you find the leaf furthest from the root. Keep a counter going to determine the leaves.

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  }

推荐答案

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

maxDepth(root.left) returns the max depth of the left sub tree.
maxDepth(root.right) returns the max depth of the right sub tree.
The max of these two is the maximal sub tree depth.
Adding 1 for the root node, you get the max depth of the tree.

假设这是树:

            A
         B      C
       D   E   F   G
     H
   I

只需查看一下即可看到最大深度为5(由路径A-B-D-H-I形成)，最小深度为3(由多个路径形成，例如A-C-G).

Just by looking at it you can see the max depth is 5 (formed by the path A-B-D-H-I) and the min depth is 3 (formed by several paths, for example A-C-G).

现在，最大深度为1(对于根A)+两个子树的最大深度.
根为B的第一个子树的最大深度为4(B-D-H-I).根为C的第二个子树的最大深度为2(C-F).
max(4,2)= 4
因此，整棵树的最大深度为1 + max(4,2)= 5.

Now, the max depth is 1 (for the root A) + the max depth of the two sub trees.
The first sub tree, whose root is B has max depth 4 (B-D-H-I). The second sub tree, whose root is C has a max depth 2 (C-F).
max(4,2) = 4
Therefore the max depth of the entire tree is 1 + max(4,2) = 5.

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

If we use the letter in my sample tree to represent the sub-trees rooted in those nodes, we get :

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.

Similarly, for calculating the min depth, you calculate the min depth of the two (left and right) sub-trees, take the minimum of the two, and add 1 for the root.

这篇关于了解如何计算二叉树的深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！