leetcode103. 두 갈래 나무의 톱날 모양 차원이 두루 다니다

1556 단어 면접 문제leetcode

1. 제목 설명


두 갈래 나무를 정해서 노드 값을 되돌려주는 톱날 모양의 차원을 두루 훑어본다.(즉, 먼저 왼쪽에서 오른쪽으로, 다시 오른쪽에서 왼쪽으로 다음 층을 훑어보며, 이와 같이 층과 층 사이를 교체하여 진행한다.)
예를 들어 두 갈래 나무[3,9,20,null,null,15,7],
3/\9 20/\15 7은 다음과 같이 앤티앨리어싱 계층을 반복합니다.
[   [3],   [20,9],   [15,7] ]
출처: 리코드(LeetCode) 링크:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal저작권은 인터넷 소유에 귀속된다.상업 전재는 정부에 연락하여 권한을 부여하고, 비상업 전재는 출처를 명시해 주십시오.

2. 문제풀이 사고방식


현재 행의 수가 홀수 행인지 짝수 행인지 판단하는 데 사용할 표지 위치를 설정합니다. 홀수 행이면 임시 목록에 가입하고 짝수 행이면 임시 목록에 역방향으로 가입합니다.

3. 코드 구현

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

class Solution(object):
    def zigzagLevelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if not root:
            return res
        #  
        flag = False
        cur = [root]
        while cur:
            next = []
            ans_value=[]
            for node in cur:
                if not flag:
                    ans_value.append(node.val)
                else:
                    ans_value.insert(0,node.val)
                if node.left:
                    next.append(node.left)
                if node.right:
                    next.append(node.right)
            res.append(ans_value)
            flag = not flag
            cur = next
        return res

좋은 웹페이지 즐겨찾기