二叉树的高度
考虑以下代码：
public int heightOfBinaryTree(Node node)
{
if (node == null)
{
return 0;
}
else
{
return 1 +
Math.max(heightOfBinaryTree(node.left),
heightOfBinaryTree(node.right));
}
}
我想知道这段代码背后的逻辑推理。人们是怎么想出它的？有归纳证明吗？
而且，我想到只用二叉树的根作为参数进行 BFS 来获取二叉树的高度。以前的方法比我的好吗？为什么？
Consider the following code:
public int heightOfBinaryTree(Node node)
{
if (node == null)
{
return 0;
}
else
{
return 1 +
Math.max(heightOfBinaryTree(node.left),
heightOfBinaryTree(node.right));
}
}
I want to know the logical reasoning behind this code. How did people come up with it? Does some have an inductive proof?
Moreover, I thought of just doing a BFS with the root of the binary tree as the argument to get the height of the binary tree. Is the previous approach better than mine?Why?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
叶节点的子节点为
null。因此，这就是说，一旦我们越过了叶子，就不再有节点了。如果我们没有超过叶节点，我们必须计算高度，并且此代码递归地执行此操作。
当前节点将当前计算的子树的高度加1。
我们递归地计算左子树 (
node.left) 和右子树 (node.right) 的高度。由于我们正在计算最大深度，因此我们取这两个深度中的最大值。我上面已经证明了递归函数是正确的。所以调用父节点上的函数就会计算出整棵树的深度。
以下是 本文档。
h是树的高度，hl和hr分别是左右子树的高度。您提供的代码是 DFS 的一种形式。由于必须处理所有节点才能找到树的高度，因此 DFS 和 BFS 之间不会有运行时差异，尽管 BFS 将使用 O(N) 内存，而 DFS 将使用 O(logN) 内存。 BFS 的代码也稍微复杂一些，因为它需要一个队列，而 DFS 使用“内置”递归堆栈。
The children of leaf nodes are
null. Therefore this is saying that once we've gone past the leaves, there are no further nodes.If we are not past the leaf nodes, we have to calculate the height and this code does so recursively.
The current node adds a height of 1 to the height of the subtree currently being calculated.
We recursively calculate the height of the left subtree (
node.left) and right subtree (node.right). Since we're calculating the maximum depth, we take the maximum of these two depths.I've shown above that the recursive function is correct. So calling the function on the parent node will calculate the depth of the entire tree.
Here's a graphical representation of the height of a tree from this document.
his the height of the tree,hlandhrare the heights of the left and right subtrees respectively.The code you provided is a form of DFS. Since you have to process all nodes to find the height of the tree, there will be no runtime difference between DFS and BFS, although BFS will use O(N) memory while DFS will use O(logN) memory. BFS is also slightly more complex to code, since it requires a queue while DFS makes use of the "built-in" recursive stack.
该代码背后的逻辑是：
由于一个节点将有两个子节点，因此树的高度将是其根为左子节点和右子节点的树的高度的最大值，当然，对于到子节点的步行，树的高度将是+1。
正如你所看到的，上面的描述是递归的，代码也是如此。
BFS 也应该这样做，但无论是实现还是空间/时间复杂性，这都有点过分了。
有句话说，递归函数虽然很难理解，但是实现起来却非常优雅。
The logic behind that code is:
since a node will have two children, the height of the Tree will be maximum of the heights of tree whose roots are the left child and right child, and of course +1 for the walk to the children.
As you can see, the description above is recursive and so is the code.
BFS should also do, but it would be an overkill as both implementation and space/time complexity.
There is a say, recursive functions though hard to understand, but are very elegant to implement.
树的高度是从其根部开始的最长向下路径的长度。
该函数是一种计算二叉树层数的递归方法。它只是在树下降时增加计数器，返回最大计数器（最低节点上的计数器）。
我希望我有所帮助。
The height of a tree is the length of longest downward path from it's root.
This function is a recursive way to count the levels of a binary tree. It just increments counters as it descends the tree, returning the maximum counter (the counter on the lowest node).
I hope I have helped.
这是一个递归函数。也就是说，一棵树的高度是 1 + 其最高树枝的高度。
BFS是广度优先搜索吗？我不确定效率上会有什么区别，但我喜欢递归函数的简单性。
It's a recursive function. It's saying the height of a tree is 1 + the height of its tallest branch.
Is BFS a breadth first search? I'm not sure what difference there would be in efficiency, but I like the simplicity of the recursive function.
扩展更多答案并详细说明递归和递归调用堆栈。
假设树
首先假设左子树，root(2) 在左子树上调用
heightOfBinaryTree方法该方法的调用堆栈将如下所示
考虑到这些调用， 在方法返回任何内容之前进行。
迭代递归调用堆栈，这是每个节点返回其输出的地方。
右子树也是如此。如果我们比较左子树和右子树的输出，我们就会得到高度。
To extend more on the answers and elaborate more on recursion plus recursive call stack.
Suppose the tree
lets suppose the left sub-tree first, root(2) called the
heightOfBinaryTreemethod on the left sub-treeThe call stack of the method in question will be as follows
consider that fact these calls are made before the method returned anything.
iterating back on the recursive call stack, this is where each node return its output.
Same goes for the right sub-tree. If we compare the output from both left and right sub-tree we will have the height.