給定規格的二叉樹中節點的最優化位置是什麼？

Question

假設我有一棵二叉樹，其中一個節點可以有0,1或2個子節點。成本值與每個節點相關聯，並且可以是{5,10,20,40}。新節點的最佳佈局位於具有相同或更低成本值的節點下。例如，一個成本值爲20的新節點最好置於成本值爲20的節點下，但也可以放置在成本值爲5和10的節點下。

該算法的主要要求是完成左側如果需要，也就是說，如果一個成本值爲10的節點具有成本值爲10的左側子節點，則具有成本值10的新節點將成爲上述節點的右側子節點。次要要求是最大化樹的整體深度。

該樹無法在任何時間點重新排列。如果一個傳入節點的價值較低，那麼就沒有懲罰。 鑑於上述要求，我們如何確定樹中傳入新節點的最佳位置？我們可以爲它編寫一個通用算法嗎？

最初，我想先完成樹的每個級別，但我認爲這不是最優的。

Answer 1

第二個要求是最大化樹的整體深度。

這有點不尋常。

的最快方法：

1. 排序您的輸入值
2. 填補所有的最低值節點與第一項要求（目前還不清楚如果兩個左右節點必須在之前充滿尊重（5'S）如果它必須是那麼最大深度將是log2（N ）如果允許「沒有填充右邊的情況下進入深處」，那麼最大深度樹將在列表中完全退化節點爲空）。此
   呼叫主樹
3. 從下一個值使得一樹（比方說10 - 值的節點）和此樹連接到
4. 重複步驟3在必要時主樹

注意的最深分支：這是最簡單的概念，實現可能會利用主樹一直排序的事實，並利用初始排序來完成。