트리를 통해 탐색

Question

트리의 모든 요소를 ​​목록에 반환하는 함수를 작성하고 싶습니다. 글로벌 변수를 사용할 수 없다. 여기에 내가 시도 내용은 다음과 같습니다

def traverse(current node):  
    if no left child and no right child: 
     return current nodes data 
    else: 
     if both left child and right child exist: 
      return [current nodes data,left_child.traverse(),right_child._traverse()] 
     elif no left child: return [current node's data,right_child.traverse()] 
     elif no right child: return [current node's data,left_child.traverse()] 

우리는이 예를 사용 : (루트는 2, 왼쪽 아이는 1, 바로 아이가 3과 오른쪽 아동의 권리 자녀 4입니다)

2 
1  3 
      4 

트래버스에 전화를 그래서 유일한 문제는 우리가 모두 하나 개의 목록에 맞도록 얻을 수 있다는 것입니다

[2, 1, [3, 4]]

:이 나무는이 돌아왔다.

편집 : node.data, node.left, node.right

Answer 1

대신 값 목록을 반환하는 당신이 배열을 전달하고 반복적으로 값을 추가 할 : 다음 호출 할 수있는 노드의 기능 중 일부입니다 배열 : 당신은 호출하여 목록을 얻을 것

def traverse(node, arr): 
    if node.left: 
     traverse(node.left, arr) 
    arr.append(node.data) 
    if node.right: 
     traverse(node.right, arr) 
    return arr # this is for convenience so we don't have to store arr 

:

traverse(node, []) 

Answer 2

문제는 각 함수 호출이 새 목록을 작성하고 기존 목록에 추가하는 것입니다. 대신 기존 목록에 자식 노드를 추가하려고합니다. 여기

은 명시 적으로 호출 사이 목록 전달에 의존하지 않는 재귀 솔루션 :

def traverse(node): 
    if node.left and node.right: 
     return [node.data] + traverse(node.left) + traverse(node.right) 
    elif node.left: 
     return [node.data] + traverse(node.left) 
    elif node.right: 
     return [node.data] + traverse(node.right) 
    else: 
     return [node.data]