在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

回答

相关问题