我正在解決leetcode的最大二叉樹問題。TL;DR 是你有一個數組，例如這個：[3,2,1,6,0,5]您應該獲取最大元素并將其作為樹的根。然后將數組分為該元素左側的部分和右側的部分，這些部分分別用于以相同的方式遞歸創建左子樹和右子樹。LeetCode 聲稱最佳解決方案（顯示在“解決方案”選項卡中）在每個遞歸步驟中使用線性搜索來尋找子數組的最大值。在最壞的情況下，這是 O(n^2)。這是我想出的解決方案，而且很簡單。然而，我正在查看其他提交的內容并找到了線性時間解決方案，但我很難理解它是如何工作的！它看起來像這樣：def constructMaximumBinaryTree(nums): nodes=[] for num in nums: node = TreeNode(num) while nodes and num>nodes[-1].val: node.left = nodes.pop() if nodes: nodes[-1].right = node nodes.append(node) return nodes[0]nodes我已經分析了這個函數，總的來說，這似乎是線性時間 (O(n))，因為每個唯一節點最多添加到數組中并從數組中彈出一次。我嘗試使用不同的示例輸入來運行它，但我正在努力將這些點連接起來并理解它是如何工作的。有人可以向我解釋一下嗎？
1 回答
qq_遁去的一_1
TA貢獻1725條經驗 獲得超8個贊
理解該算法的一種方法是考慮循環不變量。在這種情況下， 的數組nodes始終滿足在每次執行 之前和之后的條件for-loop：
nodes為空且最大二叉樹不存在（例如，如果輸入nums為空）中的第一項
nodes是基于迄今為止從輸入處理的數據的最大二叉樹nums
確保while-loop當前最大二叉樹是數組中的第一項nodes，否則，它將被彈出并添加為left子樹。
在 的每次迭代期間for-loop，檢查：
if nodes: nodes[-1].right = node
將當前節點作為右子樹添加到數組中的最后一項nodes。當發生這種情況時，當前節點小于數組中的最后一個節點nodes（因為每個輸入整數被定義為唯一）。并且由于當前節點小于數組中的最后一個節點，因此最后一個節點充當其值大于當前項的分區點，這就是為什么將當前節點添加為右子樹。
當數組中有多個項目時nodes，每個項目都是其左側項目的子樹。
運行時間
對于運行時間，令n為輸入的長度nums。for 循環執行了n次。如果輸入數據按降序排序，但最大輸入值位于輸入末尾（例如：4、3、2、1、5），則每次迭代期間將跳過內部 while 循環，直到最后一次 for 循環迭代。在最后一次 for 循環迭代期間， while 循環將運行n - 1次，總運行時間為n + (n - 1) => 2n - 1 => O(n)。
添加回答
舉報
0/150
提交
取消