java - 二叉树的高度

Question

考虑以下代码:

public int heightOfBinaryTree(Node node)
{
    if (node == null)
    {
        return 0;
    }
    else
    {
        return 1 +
        Math.max(heightOfBinaryTree(node.left),
            heightOfBinaryTree(node.right));
    }
}

我想知道这段代码背后的逻辑推理。人们是怎么想出来的？有些人有归纳证明吗？

此外，我想只用二叉树的根作为参数进行 BFS 以获得二叉树的高度。以前的方法比我的好吗？为什么？

Answer 1

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

叶子节点的子节点是null。因此，这就是说，一旦我们经过叶子，就没有更多的节点了。

如果我们没有经过叶子节点，我们必须计算高度，这段代码递归地计算。

return 1 +

当前节点在当前正在计算的子树的高度上加一高度。

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

我们递归计算左子树(node.left)和右子树(node.right)的高度。由于我们正在计算最大深度，因此我们取这两个深度中的最大值。

我已经在上面证明了递归函数是正确的。所以调用父节点上的函数会计算整棵树的深度。

这是 this document 中一棵树的高度的图形表示. h 是树的高度，hl 和 hr 分别是左右子树的高度。

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?

您提供的代码是 DFS 的一种形式。由于您必须处理所有节点才能找到树的高度，因此 DFS 和 BFS 之间没有运行时差异，尽管 BFS 将使用 O(N) 内存，而 DFS 将使用 O(logN) 内存。 BFS 的代码也稍微复杂一些，因为它需要一个队列，而 DFS 使用“内置”递归堆栈。