我正在研究 Leet Code 問題
輸入： root = [1,2,3,4,5]
輸出： 3
解釋： 3是路徑的長度[4,2,1,3]或[5,2,1,3]。
這是我的嘗試：
def diameterOfBinaryTree(self, root):
return self.getHeight(root.left) self.getHeight(root.right)
def getHeight(self, root):
if not root:
return 0
return max(self.getHeight(root.left), self.getHeight(root.right)) 1
我通過了100/104 個測驗用例。
我出錯的測驗用例的輸入為[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]，預期結果為8。但是，由于我的解決方案的邏輯，我得到了7并且不知道我怎么會錯。
uj5u.com熱心網友回復：
我出錯的唯一測驗用例的輸入為 [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6 ,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2] ... 不知道我怎么可能是錯的。
提供的樹看起來像這樣：
___4___
/ \
-7 ___-3_____
/ \
___-9___ -3
/ \ /
9 -7 -4
/ / \
__6__ -6 -6
/ \ / /
0 6 5 9
\ / /
-1 -4 -2
最長的路徑確實是 8，因為以 -9為根的子樹中最長的路徑具有最長的路徑。您的代碼找不到最長的路徑，因為它要求根是其中的一部分。
因此，您應該檢查任何子樹的最長路徑（遞回）并保留這些選項中最長的路徑：
- 在左子樹中找到的最長路徑
- 在右子樹中找到的最長路徑
- 通過包含根可以形成的最長路徑（即左高度 右高度 1）
您的代碼沒有考慮前兩個選項，而始終考慮第三個選項。
以上是在這個（隱藏的）解決方案中實作的。先自己試試：
class Solution(object):
def diameterOfBinaryTree(self, root):
self.longestPath = 0
def levels(node): # With side-effect: it updates longestPath
if not node:
return 0
leftLevels = levels(node.left)
rightLevels = levels(node.right)
self.longestPath = max(self.longestPath, leftLevels rightLevels)
return 1 max(leftLevels, rightLevels)
levels(root) # Not interested in the returned value...
return self.longestPath # ...but all the more in the side effect!
uj5u.com熱心網友回復：
您的代碼假定diameter of the binary tree將始終通過root，但情況并非如此。您必須考慮具有更長直徑的子樹。一種方法可以在下面找到，它是您代碼的稍微修改版本：
class Solution(object):
maximum = 0
def getHeight(self, root):
if not root:
return 0
left = self.getHeight(root.left)
right = self.getHeight(root.right)
sub_diameter = left right
if(self.maximum < sub_diameter): self.maximum = sub_diameter
return max(left, right) 1
def diameterOfBinaryTree(self, root):
return max(self.getHeight(root.left) self.getHeight(root.right), self.maximum)
經測驗，它通過了所有測驗用例。
主要邏輯是保留子樹的最大直徑值，并與最后通過根的直徑進行比較。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313575.html
上一篇：找到影像最佳壓縮級別的最快方法
下一篇：計算給定陣列的最小成本