검지offer-32.위에서 아래로 두 갈래 트리 인쇄(차원 반복/폭 우선 검색)★

제목 출처:
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/(레이어별 출력)
https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/(레이어별로 지그재그 출력)
생각:
깊이 우선 검색은 창고의 선입후출 특징을 이용하고 광도 우선 검색은 대열의 선입후출 특징을 이용한다.
코드:
사실은 먼저 훑어보는 것이다. 단지 팝이 나오는 것이 대열의 첫 번째 요소일 뿐이다.

# 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 levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        res = []
        q = [root]        #  
        while q:
            node = q.pop(0)      #  ， 
            res.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        return res        

한 레이어에 한 줄을 내보내려면 대기열 끝에 현재 노드의 좌우 트리를 추가할 때마다 한 개 이상의 내부 순환을 수행합니다.

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        q = [root]
        while q:
            tmp = []
            for i in range(len(q)):        
                node = q.pop(0)
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(tmp)
        return res

만약 지그재그로 층별로 출력을 요구한다면, 로고를 추가하거나res의 항수에 따라 현재 홀수층인지 짝수층인지 판단합니다.

class Solution(object):
    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        q = [root] 
        flag = 1
        while q:
            tmp = []
            for i in range(len(q)):
                node = q.pop(0)
                tmp.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            res.append(tmp if flag==1 else tmp[::-1])     # flag 1 ， 
            flag *= -1     #  
        return res