Collection of binary tree topics

One 、 Sequence traversal of binary tree （ Breadth search ） Print binary tree from top to bottom

Using queue First in, first out principle ：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        List ,queue= [], collections.deque()
        queue.append(root)
        
        while(queue):
            node = queue.popleft()
            List.append(node.val)

            if node.left !=None:
                queue.append(node.left)
            if node.right !=None:
                queue.append(node.right)
        return List

Two 、 Binary tree output by layer   Print binary tree from top to bottom II

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        List = []
        que = collections.deque()

        que.append(root)
        while(que):
            sublist = []
            for node in range(len(que)):
                node = que.popleft()
                sublist.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            List.append(sublist)
        return List

3、 ... and 、 Zigzag Print binary tree ： Print binary tree from top to bottom III

1. According to the binary tree sequence traversal method ： Even level flashback output , Odd layer positive sequence output ;（ Method 1 ）

2. Use two deque , When it is an even number of layers , Use left insert ; Insert on the right when there are odd layers

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []       
        List,que = [],collections.deque()
        que.append(root)
        high = 0
        while(que):
            high+=1
            sublist = collections.deque()
            for _ in range(len(que)):
                node = que.popleft()
                if high%2==0:    
                    sublist.appendleft(node.val)
                else:
                    sublist.append(node.val)

                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            List.append(list(sublist))


        return List