一千萬個為什麽

搜索

二叉樹值中的下一個最大值

給定一個節點,要找到下一個最大值,有兩種情況:

  • 首先:如果節點有一個正確的孩子。如果是,則下一個最大值位於其右子的左子樹的最左側。

  • 第二:如果節點是葉子,則下一個最大值在其父節點之一。哪個是父母呢?

謝謝!

最佳答案

你的第一個案例是完全正確的。但是,第二種情況應改為:

2)如果節點沒有正確的子節點(註意:這並不意味著它是一片葉子!),那麽你必須想知道從節點到根的(唯一)路徑,直到你輸入一個大於它的父節點。兒童。該父節點是下一個更大的節點。如果不存在這樣的父節點,那麽我們開始的節點是樹中最大的節點。

轉載註明原文: 二叉樹值中的下一個最大值