求二叉树的高度

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;
   }
 } 
}

例子是：

身高是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); ---> 一直到 最右边的 节点 ??

如果我有以下树会怎样：

并且高度为 5 因为 3->5->4->3->2?

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

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

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

提前致谢！

Answer 1

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

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

在递归算法中，你总是有一个递归步骤（在这种情况下是第二步）和一个停止递归的基本情况（没有节点的树）。

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

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

   5              2
  / \            /
 1   4          6
               /
              7

这就是

所做的

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

然后递归，高度为

   5
  / \
 1   4

是子树高度之间的最大值

 1   4

等等。

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

Answer 2

具体回答您的问题：

1) 您突出显示的两行：

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

树的高度不加1。相反，他们将左侧 sub-tree 和右侧 sub-tree 的高度分配给两个单独的变量。

下面赋值后的if-then-else-branch是高度加1的代码：

if(left > right) {
    return 1 + left;
} else {
    return 1 + right;
}

2) 两次递归调用：

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

不完全去只是树的最左边和最右边的节点，它们访问了根节点左边children的所有节点和对 children 在根节点上。最终将访问所有节点。

用递归解决通常是一种优雅的方法，但将其视为解决较小的问题并构建解决方案会有所帮助，而不是试图在脑海中描绘出整个解决方案。

让我们运行通过您发布的示例。

使用递归，首先找出2下方的children的高度，即0，即可计算出高度。

求子树的高度：

它会将下面的子树的高度加 1，即 0，从而使我们的高度为 1。

然后子树的高度加1：

  3
 /
2

给我们 1 + 从 2 = 2 开始的子树的高度。

这将继续向上子树：

1 + 从 3 开始的子树的高度 = 1 + (2) = 3

然后：

最后是主树：

递归算法通过查找较小子树的高度来解决查找树的高度的问题。

求二叉树的高度

Finding the height of the binary tree

java

binary-search-tree