java - 求二叉树的高度

Question

给出查找二叉树高度的代码:

/*
class Node 
int data;
Node left;
Node right;
*/
int height(Node root)
{
   if(root == null){
   return 0;
}
else{
   int left = height(root.left);
   int right = height(root.right);
   if(left > right){
       return 1 + left;
   }
   else{
       return 1 + right;
   }
 } 
}

示例是:

     3
   /   \
  5     2
 / \    /
1   4  6
      /
     7

高度为4，因为3->2->6->7

我在理解这里的递归过程时遇到了很大的麻烦。如果有人向我解释以下问题，我将不胜感激:

1)遍历树时，下面两行在每次访问节点时是否加1？更大的问题:它是如何工作的？

 int left = height(root.left);
 int right = height(root.right);

2)我理解正确吗？:int left = height(root.left); ---> 直到最左边节点??int right = height(root.right); ---> 直到最右边节点??

如果我有以下树会发生什么:

     3
   /   \
  5     2
 / \    /
1   4  6
   /  /
  3  7
 /
2

由于3->5->4->3->2，高度将是5？

我很难理解这些行的递归:

int left = height(root.left);
int right = height(root.right);

我对这些行的理解是 left 转到最左边的节点，而 right 转到最右边的节点。

提前致谢!

Answer 1

基本上，您有一个简单的算法描述，并且几乎可以按字面意思实现它以获得递归解决方案。你从这样的事情开始:

• 没有节点的树的高度为 0
• 具有任意数量节点的树的高度为 1 + 左子树和右子树之间的最大高度

在递归算法中，您总是有一个递归步骤(在本例中是第二步)和一个停止递归的基本情况(没有节点的树)。

所以根部树的高度基本上为 3

     3
   /   \
  5     2
 / \    /
1   4  6
      /
     7

是1 + 从3开始的两个子树的高度之间的最大值，例如:

   5              2
  / \            /
 1   4          6
               /
              7  

这就是这样做的

int left = height(root.left);
int right = height(root.right);

然后递归，高度为

   5
  / \
 1   4

是子树高度之间的最大值

 1   4

等等。

基本上，在每个递归步骤中，您将执行路径分成 2 部分来计算子树的高度，当计算出两个子树的高度时，您将取较大的高度，加 1 并返回值。