考虑以下code：

 公众诠释heightOfBinaryTree（节点节点）
{
    如果（节点== NULL）
    {
        返回0;
    }
    其他
    {
        返回1 +
        Math.max（heightOfBinaryTree（node.left）
            heightOfBinaryTree（node.right））;
    }
}
 

我想知道这背后code中的逻辑推理。人们是如何得出的呢？有没有一些有一个归纳证明？

此外，我还以为只是做了BFS与二叉树作为参数的根得到二叉树的高度。是previous方法比我好？为什么？

 如果（节点== NULL）
{
    返回0;
}
 

叶节点的孩子是空。因此，这是说，一旦我们没了往日的叶子，没有更多的节点。

如果我们不是过去的叶节点，我们要计算的高度，这code这样做递归。

 返回1​​ +
 

当前节点增加了1的高度，以当前正在计算的子树的高度

  Math.max（heightOfBinaryTree（node.left）
        heightOfBinaryTree（node.right））;
 

我们递归地计算左子树的高度（ node.left ）和右子树（node.right ）。由于我们计算的最大深度，我们取这两个深度的最大值。

我已经证明上面的递归函数是正确的。因此调用父节点上的功能将计算整个树的深度。

下面是一棵树，从this文档。 ^ h 是树的高度， HL 和小时是左和右子树的高度分别

此外，我还以为只是做了的   BFS与二进制树的根   作为参数来获得的高度   二进制树。是previous   比我更好的办法呢？为什么？

您提供的code是DFS的一种形式。因为你必须处理所有节点，找到树的高度，就会有DFS和BFS之间没有运行差异，虽然BFS将使用O（N）的内存，而DFS将使用O（logN）的内存。 BFS也稍微复杂一些，以code，因为它需要一个队列，而DFS利用了内置递归栈。

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?

if (node == null)
{
    return 0;
}

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.

return 1 +

The current node adds a height of 1 to the height of the subtree currently being calculated.

    Math.max(heightOfBinaryTree(node.left),
        heightOfBinaryTree(node.right));

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. h is the height of the tree, hl and hr are the heights of the left and right subtrees respectively.

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?

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.