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

我正在通过职业杯指南作为通过基本CS主体的速成课程，并坚持计算二叉树的最小/最大深度的示例。由于这是几乎所有例子，我认为我会在这里发表一个问题。了解如何计算二叉树的深度

该指令旨在实现一种方法，该方法将检查树是否平衡。为了做到这一点，你需要比较最小深度和最大深度，并确保它们之间的差值不大于1。这个原则就像它所得到的一样简单。第15行的方法是为了做到这一点。

但是，我不明白每个帮助程序方法（和minDepth）的返回语句是怎么回事。如何从root.left或root.right派生出一个数字？是否Math.max功能简单地假设一个1或0是有值/空节点，或者，由于被指定值（只是Node对象），确实Math.max(maxDepth(root.left), maxDepth(root.right)本身等于0，从而增加由1直到返回值两个节点都是空的？

如果所以这是用于计算一个树的最小/最大深度的一般过程：

minDepth =没有根有孩子吗？ 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 }

来源

2014-07-22 NealR

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

想这是树：

  A 
     B  C 
     D E F G 
    H 
    I

只要看一眼就可以看到的最大深度为5，最小深度（由路径ABDHI形成）是3（由多条路径形成，例如ACG）。

现在，最大深度为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为根。

来源

2014-07-22 22:33:03 Eran

这就是我没有遵循的：maxDepth（root.left）如何返回树的深度？ – NealR

@NealR'maxDepth（root.left）'返回子树的最大深度，其根是原始树的根的左子。如果您对递归不熟悉，则需要时间来习惯它（并且相信它实际上可行）。 – Eran

对不起，在这里头很重，但是这些数字（最大深度）是如何计算的？ – NealR

嗯，这是一个递归函数，它检查树的两边，然后将结果与max或min进行比较。

图片帮助。

 o go left and right 
    / \ 
(+1)o  o(+1)  
    \  
    o(+1)

所以让我们把它带回代码。

return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));

调用堆栈会是这个样子

// max return 2 
- left +1      
    // max return 1 
    -left 0      
    -right +1 
     // max return 0 
     -left 0     
     -right 0 
- right +1 
    //max return 0 
    -left 0 
    -right 0

Min作品本质上是相同的方式。

来源

2014-07-22 22:39:23 progrenhard

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

回答

相关问题