一千萬個為什麽

搜索

二叉樹的高度

請考慮以下代碼:

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

我想知道這段代碼背後的邏輯推理。人們是怎麽想出來的?有些人有歸納證明嗎?

此外,我想到只用二叉樹的根作為參數獲取二叉樹的高度。以前的方法比我的好嗎?為什麽?

最佳答案

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

葉節點的子節點是 null 。因此,這就是說,一旦我們走過樹葉,就沒有其他節點了。

如果我們沒有超過葉節點,我們必須計算高度,這個代碼遞歸。

return 1 +

當前節點將高度1添加到當前正在計算的子樹的高度。

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

我們遞歸地計算左子樹( node.left )和右子樹( node.right )的高度。由於我們正在計算最大深度,因此我們取這兩個深度的最大值。

我已經在上面說明了遞歸函數是正確的。因此,在父節點上調用該函數將計算整個樹的深度。

這是來自本文件h 是樹的高度, hlhr 分別是左右子樹的高度。

而且,我想到了   BFS與二叉樹的根   作為獲得高度的論據   二叉樹。是以前的   比我的方法更好?為什麽?

您提供的代碼是DFS的一種形式。由於必須處理所有節點以查找樹的高度,因此DFS和BFS之間不存在運行時差異,盡管BFS將使用O(N)內存,而DFS將使用O(logN)內存。 BFS的代碼也稍微復雜一些,因為它需要一個隊列,而DFS則使用“內置”遞歸堆棧。

轉載註明原文: 二叉樹的高度