树的层序遍历

递归法关键在于如何构建res这个数据结构

def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root:
            return []
        res = []
        def dfs(index,r):
            # 假设res是[ [1],[2,3] ]， index是3，就再插入一个空list放到res中
            if len(res)<index:
                res.append([])
            #  将当前节点的值加入到res中，index代表当前层，假设index是3，节点值是99
            # res是[ [1],[2,3] [4] ]，加入后res就变为 [ [1],[2,3] [4,99] ]
            res[index-1].append(r.val)
            # 递归的处理左子树，右子树，同时将层数index+1
            if r.left:
                dfs(index+1,r.left)
            if r.right:
                dfs(index+1,r.right)
        dfs(1,root)
        return res

作者：wang_ni_ma
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/die-dai-di-gui-duo-tu-yan-shi-102er-cha-shu-de-cen/
来源：力扣（LeetCode）

迭代法关键在于栈操作如何判断某一层的开始和结束

def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
        return res

作者：jyd
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Z星遍历

def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        res=[]
        # def PrintTree(layer,root):
        #     if not root:
        #         return
        #     res.append(root.val)
        #     if layer%2==1:
        #         PrintTree(layer+1,root.right)
        #         PrintTree(layer+1,root.left)
        #     else:
        #         PrintTree(layer+1,root.left)
        #         PrintTree(layer+1,root.right)
        stack=collections.deque()
        stack.append(root)
        flag=1
        while stack:
            n=len(stack)
            tmp=[]
            for _ in range(n):

                if flag==-1:
                    cur=stack.pop()
                    tmp.append(cur.val)
                    if cur.right:stack.appendleft(cur.right)
                    if cur.left:stack.appendleft(cur.left)
                else:
                    cur=stack.popleft()
                    tmp.append(cur.val)
                    if cur.left:stack.append(cur.left)
                    if cur.right:stack.append(cur.right)
            flag*=-1
            res.append(tmp)
        return res