在python

一二進制樹的最大深度我從二進制樹中創建的元組，它看起來像這樣：在python

元組=（1，（2，（4,5,6），（7，無，8）），（3,9，（10,11,12）））

的樹狀結構變爲通過應用壓痕更加清晰：

我知道如何尋找最大二叉樹的深度使用遞歸方法，但我試圖找到我們的最大深度我創建的元組。任何人都可以幫助我如何做到這一點？

來源

2017-08-31 Invariance

對此進行一次刺探，看看會發生什麼。 – wwii

也可以在元組表單上使用遞歸。 –

只要你有內存，我會假設無限，但找到深度的遞歸函數可能會碰到python的遞歸限制（你可以在設置中改變它）。把它轉換成一個迭代函數，也許通過使用堆棧，是解決這個問題的更好方法。 –

遞歸方法：

a = (1,(2,(4,5,6),(7,None,8)),(3,9,(10,11,12))); 

def depth(x): 
    if(isinstance(x, int) or x == None): 
     return 1; 
    else: 
     dL = depth(x[1]); 
     dR = depth(x[2]); 
     return max(dL, dR) + 1; 

print(depth(a));

的想法是通過觀察其左，右子樹來確定樹的深度。如果節點沒有子樹，則返回深度1。否則它返回最大值（深度，左側深度）+ 1

來源

2017-08-31 13:47:35

這是一個棘手但相當有效的解決方案，只要數據結構的元素不是包含'('或')'的字符串即可。我會將元組轉換爲字符串，並解析它以計算括號的深度。

string = str(myTuple) 

currentDepth = 0 
maxDepth = 0 
for c in string: 
    if c == '(': 
     currentDepth += 1 
    elif c == ')': 
     currentDepth -= 1 

    maxDepth = max(maxDepth, currentDepth)

它給出與到其中的元組被轉換的字符串在問候的字符數以線性時間的深度。這個數字應該或多或少與元素的數量加上深度成正比，所以你的複雜度有點等於O(n + d)。

來源

2017-08-31 13:32:42

...假設樹的任何值都不是包含（或）的字符串。 –

@tobias_k沒有辦法發生這種情況:)添加它作爲一個警告，感謝您指出。 –

class Node(object): 
    def __init__(self, x): 
     self.val = x 
     self.left = None 
     self.right = None 

class Solution(object): 
    def maxDepth(self, root): 
     if not root: 
      return 0 
     ldepth = self.maxDepth(root.left) 
     rdepth = self.maxDepth(root.right) 
     return max(ldepth, rdepth) + 1

來源

2017-12-20 18:13:05

回答

相關問題