如何在描述二叉树的列表中找到深度

Question

例如：

[[7, 0, 0], [2, 10, 11], [4, 9, 0], [6, 0, 0], [1, 8, 12], [9, 0, 2], [13, 0, 6], [5, 4, 3], [12, 0, 0], [10, 0, 0], [11, 0, 0], [3, 1, 13], [8, 7, 0]] Root=5

一个列表包含一个子列表，第一个值是节点，第二个值是左边的children，第三个是右边的children。0表示没有children on left/right,想求每个节点的深度，提取相同深度的节点。

p = lable.index(r)    
depth_list = []    
depth = 0    
depth_list.append([r, 0])    
while lable_left_right[p][1] != 0 or lable_left_right[p][2] != 0:    
    depth += 1    
    left = lable_left_right[p][1]    
    right = lable_left_right[p][2]   
    if left == 0 and right != 0:    
        p = right    
        depth_list.append([p, depth])   
        continue   
    if right == 0 and left != 0:   
        p = left   
        depth_list.append([p, depth])   
        continue
    if left != 0 and right != 0:
        p = right
        depth_list.append([p, depth])
        p = left
        depth_list.append([p, depth])    
        continue

其中lable是所有节点的列表（在本例中，[7,2,4,6,1,9,13,5,12,10,11,3,8]和r是根。lable_left_right是给定的列表
如果节点有两个 children 我会卡住，但我只能使用一个 p 来继续 while 循环，所以我将失去另一个 children 作为节点来完成任务。是否有可能在一个while循环的中心开始另一个while循环并继续处理原始循环？如果不是，是否有另一种方法来获取所有节点的深度？

Answer 1

这可以使用以下方法递归解决：

tree = [[7, 0, 0], [2, 10, 11], [4, 9, 0], [6, 0, 0], [1, 8, 12], [9, 0, 2], [13, 0, 6], [5, 4, 3], [12, 0, 0], [10, 0, 0], [11, 0, 0], [3, 1, 13], [8, 7, 0]]

def getRootNode():
    centernodes, leftnodes, rightnodes = map(list, zip(*tree))
    for node in centernodes:
        if (node not in leftnodes) and (node not in rightnodes):
            return node

def getLeftNode(n):
    for i in range(len(tree)):
        if tree[i][0] == n:
            return tree[i][1]

def getRightNode(n):
    for i in range(len(tree)):
        if tree[i][0] == n:
            return tree[i][2]

def maxDepth(n):
    if n == 0:
        return 0
    else:
        lDepth = maxDepth(getLeftNode(n))
        rDepth = maxDepth(getRightNode(n))
        if (lDepth > rDepth):
            return lDepth+1
        else:
            return rDepth+1

n = getRootNode()
print("Root Node is " + str(n))
depth = maxDepth(n) - 1
print("Max Depth is " + str(depth))

如何在描述二叉树的列表中找到深度

How to find depth in a list descrip a binary tree

python

binary-tree

python-3.5

depth