python - python中二叉树的最大深度

Question

我从二叉树创建了一个元组，它看起来像这样:

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

通过应用缩进，树结构变得更加清晰:

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

我知道如何使用递归方法找到二叉树的最大深度，但我试图使用我创建的元组找到最大深度。谁能帮我怎么做？

Answer 1

递归方法:

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。否则它返回 max(depth of right, depth of left) + 1