목록 descrip 깊이를 이진 트리 예를 들어

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

목록은 첫 번째 값은 노드와 두 번째 값은 왼쪽에있는 아이들입니다있는 하위 목록을 포함하고 세 번째는이다 오른쪽에있는 아이들. 0은 왼쪽/오른쪽에 자식이 없음을 의미하므로 각 노드의 깊이를 찾고 동일한 깊이의 노드를 추출하려고합니다. 이 경우 모든 노드의 목록입니다 (lable

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 

는 [7,2,4,6,1,9,13,5,12,10,11,3,8] 및 r는 루트입니다. lable_left_right 노드가 두 아이가있는 경우는 내가 붙어있어 주어진 목록
하지만 난 단지 사용할 수 있습니다 one p while 루프를 계속하려면 자식 노드를 잃어 버릴 테니 하나의 while 루프의 중심에서 다른 루프를 시작하고 원래 루프를 계속 처리 할 수 ​​있습니까? 모든 노드의 깊이를 얻는 다른 방법이 있습니까?

Answer 1

이 c 다음을 사용하여 재귀 적으로 풀어야합니다.

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))