二叉树的高度

algorithm java tree

2022-09-01 05:17:47

请考虑以下代码：

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

我想知道这段代码背后的逻辑推理。人们是如何想到的？有些人有感应证明吗？

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

答案 1

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

叶节点的子节点是。因此，这是说，一旦我们越过了叶子，就没有进一步的节点了。null

如果我们没有超过叶节点，我们必须计算高度，并且此代码以递归方式执行此操作。

return 1 +

当前节点将当前正在计算的子树的高度相加 1。

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

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

我在上面已经展示了递归函数是正确的。因此，在父节点上调用函数将计算整个树的深度。

下面是本文档中树的高度的图形表示形式。是树的高度，分别是左子树和右子树的高度。hhlhr

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

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

答案 2

该代码背后的逻辑是：

由于一个节点将有两个子节点，因此树的高度将是根部为左子节点和右子节点的树的高度最大值，当然，对于步行到子节点，树的高度为+1。

如您所见，上面的描述是递归的，代码也是如此。

BFS也应该这样做，但这将是一个过度的，因为实现和空间/时间复杂性。

有一种说法，递归函数虽然很难理解，但实现起来却非常优雅。