이진 트리가 있다고 가정합니다. 지그재그 수준의 순서 순회를 찾아야 합니다. 따라서 첫 번째 행의 경우 왼쪽에서 오른쪽으로 스캔한 다음 두 번째 행에서 오른쪽에서 왼쪽으로 스캔한 다음 다시 왼쪽에서 오른쪽으로 스캔합니다. 따라서 트리가 다음과 같다면 -
순회 시퀀스는 [[3],[20,9],[15,7]]
입니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
트리가 비어 있으면 빈 목록을 반환합니다.
-
queue :=큐를 만들고 루트를 큐에 삽입하고 두 개의 빈 목록 res 및 res2를 만들고 플래그를 True로 설정
-
대기열이 비어 있지 않은 동안
-
대기열에 있는 노드 목록을 만든 다음 res에 삽입
-
대기열에 있는 노드 값 목록을 만든 다음 res2에 삽입
-
플래그가 설정되면
-
i :=res의 마지막 하위 목록 길이 – 1
-
동안 나는>=0
-
res의 마지막 하위 목록의 i번째 요소에 올바른 하위 트리가 있으면
-
대기열에 오른쪽 하위 트리 삽입
-
-
res의 마지막 하위 목록의 i번째 요소가 하위 트리를 떠났다면
-
왼쪽 하위 트리를 대기열에 삽입
-
-
i를 1 감소
-
-
-
그렇지 않으면
-
i :=res의 마지막 하위 목록 길이 – 1
-
동안 나는>=0
-
res의 마지막 하위 목록의 i번째 요소에 올바른 하위 트리가 있으면
-
대기열에 오른쪽 하위 트리 삽입
-
-
res의 마지막 하위 목록의 i번째 요소가 하위 트리를 떠났다면
-
왼쪽 하위 트리를 대기열에 삽입
-
-
i를 1 감소
-
-
-
-
res2 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def zigzagLevelOrder(self, root): if not root: return [] queue = [root] res = [] res2=[] flag = True while len(queue)!=0: res.append([i for i in queue]) res2.append([i.data for i in queue if i.data != 0]) queue = [] if flag: i=len(res[-1])-1 while i>=0: if res[-1][i].right: queue.append(res[-1][i].right) if res[-1][i].left: queue.append(res[-1][i].left) i-=1 else: i=len(res[-1])-1 while i>=0: if res[-1][i].left: queue.append(res[-1][i].left) if res[-1][i].right: queue.append(res[-1][i].right) i-=1 flag = not flag return res2 ob = Solution() tree = make_tree([3,9,20,None,None,15,7]) print(ob.zigzagLevelOrder(tree))
입력
[3,9,20,null,null,15,7]
출력
[[3], [20, 9], [15, 7]]