本文共 2072 字，大约阅读时间需要 6 分钟。

配合

先看图

class Solution:    def levelOrder(self, root: TreeNode) -> List[List[int]]:        if not root:            return []        res = []        deque = collections.deque([root])        while deque:            tmp = collections.deque()            for i in range(len(deque)):                node = deque.popleft()                # 这时候用那个长度来衡量这个层数？res                if len(res)%2==0:  # 当前是偶数层,那下一层是奇数层,尾插                    tmp.append(node.val)                else:           # 奇数层,那下一层是偶数层,头插                    tmp.appendleft(node.val)                if node.left:                    deque.append(node.left)                if node.right:                    deque.append(node.right)            res.append(list(tmp))        return res

注：

1. Python 中使用 collections 中的双端队列 方便前后插入/删除

   • pop() 方法， #从队列的 右边 删除元素，并且返回删除值
   • popleft() 方法， #从队列的 左边 删除元素，并且返回删除值
   • append(n) 方法 ，#从 右边 像队列中增加元素 ，n表示增加的元素（尾插）
   • appendleft(n) 方法，#从 左边 像队列中增加元素，n表示增加的元素（头插）
     .

2. 奇偶层的判断

   该程序段

   if len(res)%2==0:  # 当前是偶数层,那下一层是奇数层,尾插	tmp.append(node.val)else:           # 奇数层,那下一层是偶数层,头插    tmp.appendleft(node.val)

   可替代方案①：可换为 直接判断下一层的 奇偶

   if (len(res)+1)%2==0:  # 直接判断下一层是偶数层,头插	tmp.append(node.val)else:           # 直接判断下一层是奇数层,尾插 	tmp.appendleft(node.val)

   可替代方案②：deque还是双端队列，tmp是普通list。当前层tmp正常添加，添加到res中时，再判断奇偶层

   class Solution:def levelOrder(self, root: TreeNode) -> List[List[int]]:    if not root:        return []    res = []    deque = collections.deque([root])    while deque:        tmp = []        for i in range(len(deque)):            node = deque.popleft()            # 这时候用那个长度来衡量这个层数？res            tmp.append(node.val)                        if node.left:                deque.append(node.left)            if node.right:                deque.append(node.right)        res.append(tmp[::-1] if len(res)%2 else tmp)    return res

   切记：是 -1 才能倒着输出 tmp 到 res 中

   

3. 当前结果tmp要转为list列表，再添加到最终列表res中，因为此时 tmp 还是个双端队列

链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/solution/mian-shi-ti-32-iii-cong-shang-dao-xia-da-yin-er–3/

转载地址：http://myjii.baihongyu.com/