一千萬個為什麽

搜索

二叉樹中的1個子節點數

有人知道如何在具有n個節點的二叉樹中計算1個子節點(具有正好1個子節點的節點)的最大數量。請不要給我實際答案,因為這是一個功課問題,我想自己解決,但我根本不知道從哪裏開始。任何幫助都是相關的。

最佳答案

嘗試構建一個包含大量1子節點的樹。從root開始。假設root只有一個孩子。假設那個孩子本身只有一個孩子,等等。

因此,在具有$ n $節點的樹中,您可以安排除了一個以外的所有節點都有一個孩子。這意味著最大值至少為$ n-1 $,當然最多為$ n $。最後,證明最大值不是$ n $:必須至少有一個葉子(0子節點)。


我認為給定深度的樹木最大值更有趣。你可以在深度為$ n $的二叉樹中填充的1子節點的最大數量是多少?

對於深度$ 0 $,有一個葉子,所以最大值是$ 0 $。對於深度$ 1 $,枚舉顯示最大值為$ 1 $。更一般地說,什麽樹形狀最大化一子節點的數量?

轉載註明原文: 二叉樹中的1個子節點數