>source

인접한 부모가 자식 노드를 공유하는 트리를 통해 가능한 모든 경로를 생성해야합니다. 트리는 다음과 같습니다.

두 가지 트리 예 :

크기가 3 인 트리의 경우 순회는 다음과 같습니다.

크기 3 트리의 예상 출력은 다음과 같습니다.

[0,0,0]
[0,0,1]
[0,1,1]
[0,1,2]

따라서 최상위 노드는 0 번째 인덱스이고 최하위 노드는 n 번째 인덱스입니다. 이 값은 각 수준의 어떤 노드가 순회되는지를 나타냅니다.

이제 임의의 크기의 트리에 대해 트리의 위에서 아래로 가능한 모든 경로를 생성해야합니다.

나는 이와 같은 것을 시도했지만 아무 소용이 없습니다.

test = [0,0,0,0,0]
count = 0
while test[0]<5:
    for i in range(count):
        test[i] += 1
    count += 1
    print(test)

어떤 아이디어?


  • 답변 # 1

    이것이 문제에 대한 나의 대답입니다.

    def mutate(array, depth):
        new_array = []
        for path in array:
            new_array.append(path+[path[-1]])
            new_array.append(path+[path[-1]+1])
        if(depth > 2):
            return mutate(new_array, depth-1)
        else:
            return new_array
    print(mutate([[0]],5))
    mutate([0],1)
    
    

    계산 완료 성이있는 재귀 함수입니다. O(N^2)

    기본적으로이 함수는 각 재귀에 대해 하나의 레이어를 추가합니다. n- 트리의 각 경로에 대해 n + 1- 트리에 두 개의 경로가 있습니다. 하나는 n + 1 계층에서 동일한 노드 인덱스를 갖고 다른 하나는 노드 인덱스가 1 씩 증가합니다.

  • 답변 # 2

    업데이트 됨 다음 코드를 확인하십시오.

    from copy import copy 
    h = 2
    current_h = 0
    possible_paths = list()
    possible_paths.append([0])
    while current_h < h:
        new_paths = []
        for item in possible_paths:
            pow_res = pow(2,item[len(item)-1])
            item1 = copy(item)
            item2 = copy(item)
            item1.append(pow_res-1)
            item2.append(pow_res)
            new_paths.append(item1)
            new_paths.append(item2)
        possible_paths = new_paths
        current_h = current_h + 1
    print(possible_paths)
           
    
    

  • 답변 # 3

    @Sorosh 덕분에 코드를 다음과 같이 수정했습니다.

    from copy import copy 
    h = 5
    current_h = 0
    possible_paths = list()
    possible_paths.append([0])
    while current_h < h-1:
        new_paths = []
        for item in possible_paths:
            pow_res = item[current_h]
            item1 = copy(item)
            item2 = copy(item)
            item1.append(pow_res)
            item2.append(pow_res+1)
            new_paths.append(item1)
            new_paths.append(item2)
        possible_paths = new_paths
        current_h = current_h + 1
    possible_paths
    
    

    이것은 출력을 제공합니다.

    [[0, 0, 0, 0, 0],
     [0, 0, 0, 0, 1],
     [0, 0, 0, 1, 1],
     [0, 0, 0, 1, 2],
     [0, 0, 1, 1, 1],
     [0, 0, 1, 1, 2],
     [0, 0, 1, 2, 2],
     [0, 0, 1, 2, 3],
     [0, 1, 1, 1, 1],
     [0, 1, 1, 1, 2],
     [0, 1, 1, 2, 2],
     [0, 1, 1, 2, 3],
     [0, 1, 2, 2, 2],
     [0, 1, 2, 2, 3],
     [0, 1, 2, 3, 3],
     [0, 1, 2, 3, 4]]
    
    

    h의 값을 변경하면됩니다. 지금은 5 개의 '노드'가있는 전체 트리를 통과합니다.

    왜 이것이 작동하는지 완전히 모르겠습니다.

  • 이전 python - 파이 게임에서 변수에 rect가 포함되어 있는지 확인하는 방법은 무엇입니까?
  • 다음 spring - 외부 라이브러리에서 NewInstance로 생성 된 Autowire Java Bean