모든 노드에 두 개의 자식이 있는 무한 이진 트리에서 노드는 행 순서로 레이블이 지정된다고 가정합니다. 이제 홀수 행(첫 번째, 세 번째, 다섯 번째,...)에서는 레이블이 왼쪽에서 오른쪽으로, 짝수 행(두 번째, 네 번째, 여섯 번째,...)에서는 레이블이 오른쪽에서 왼쪽으로 지정됩니다. . 따라서 나무는 다음과 같을 것입니다 -
그래서 우리는 이 트리에 있는 노드의 레이블을 지정했으며, 트리의 루트에서 해당 레이블이 있는 노드까지의 경로에서 레이블을 찾아야 합니다. 따라서 입력이 레이블 =14이면 출력은 [1,3,4,14]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
두 개의 배열 트리와 res를 정의하고 트리 배열에 0과 1을 삽입하고 홀수 :=1 및 현재 :=1 및 2를 설정합니다.
-
레이블 =1이면 단일 요소가 1인 목록을 반환합니다.
-
하나의 무한 루프 생성 -
-
홀수가 0이 아니면
-
max_val :=현재 + 2
-
임시 :=max_val
-
동안 온도> 현재
-
트리에 temp 삽입
-
temp =레이블이면 루프에서 나옵니다.
-
온도 1 감소
-
-
트리의 마지막 요소가 레이블이면 루프에서 나옵니다.
-
현재 :=max_val
-
-
그렇지 않으면
-
온도 :=2
-
온도가 0이 아닌 동안
-
temp :=1, 전류를 1 증가시킨 다음 전류를 트리로 증가
-
현재 =레이블이면 루프에서 나옵니다.
-
-
트리의 마지막 요소가 레이블이면 루프에서 나옵니다.
-
-
온도 :=온도 * 2
-
홀수 :=홀수가 0이 아니면 거짓, 그렇지 않으면 참
-
-
인덱스 :=트리 길이 – 1
-
인덱스가 0이 아닌 동안
-
트리[인덱스]를 res 배열에 삽입
-
인덱스 :=인덱스 / 2
-
-
res :=res의 반전된 목록
-
반환 해상도
예제(파이썬)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
class Solution(object): def pathInZigZagTree(self, label): tree = [] res = [] tree.append(0) tree.append(1) odd = 1 current = 1 two = 2 if label == 1: return [1] while True: if odd: max_val = current + two temp = max_val while temp>current: tree.append(temp) if temp == label: break temp-=1 if tree[-1]== label: break current = max_val else: temp = two while temp: temp-=1 current+=1 tree.append(current) if current == label: break if tree[-1]== label: break two*=2 odd = not odd index = len(tree)-1 while index: res.append(tree[index]) index//=2 res=res[::-1] return res ob = Solution() print(ob.pathInZigZagTree(14))
입력
14
출력
[1,3,4,14]