LeetCode 103 [ Binary Tree Zigzag Level Order Traversal]

1577 단어

원제


두 갈래 나무를 제시하고 노드 값을 되돌려주는 톱날 모양의 차원을 반복한다(먼저 왼쪽에서 오른쪽으로, 다음 층에서 다시 오른쪽에서 왼쪽으로, 층과 층 사이를 교체한다)
두 갈래 나무 {3,9,20,#,#,15,7}
    3
   / \
  9  20
    /  \
   15   7

앤티앨리어싱으로 돌아가는 단계는 다음과 같습니다.
[
  [3],
  [20,9],
  [15,7]
]

문제 풀이 사고방식

  • 비슷한 문제 [Binary Tree Level Order Traversal]과 [Binary Tree Level Order Traversal II]
  • 역시queue로 BFS를 실현하는데 temp 결과를 처리할 때 매번 순서를 바꾸고 하나flag 변수
    • 를 빌려

    전체 코드

    # Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import Queue

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
            
        result = []
        MyQueue = Queue.Queue()
        MyQueue.put(root)
        flag = True
        while not MyQueue.empty():
            size = MyQueue.qsize()
            temp = []
            for i in range(size):
                node = MyQueue.get()
                if node.left:
                    MyQueue.put(node.left)
                if node.right:
                    MyQueue.put(node.right)
                if flag:
                    temp.append(node.val)
                else:
                    temp.insert(0, node.val)
            result.append(temp)
            flag = not flag

        return result
    링크 확인
    9도 OJ - 1350 - 두 갈래 나무의 깊이

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage