二叉树的高度

Question

请考虑以下代码:

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

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

此外,我想到只用二叉树的根作为参数获取二叉树的高度.以前的方法比我的好吗？为什么？

Answer 1

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

叶节点的子节点是null.因此,这就是说,一旦我们走过树叶,就没有其他节点了.

如果我们没有超过叶节点,我们必须计算高度,这个代码递归.

return 1 +

当前节点将高度1添加到当前正在计算的子树的高度.

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

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

我已经在上面说明了递归函数是正确的.因此,在父节点上调用该函数将计算整个树的深度.

这是本文档中树高的图形表示.h是树的高度,hl和hr分别是左,右子树的高度.

此外,我想到只用二叉树的根作为参数获取二叉树的高度.以前的方法比我的好吗？为什么？

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