LeetCode Z字形遍历二叉树

痛定思痛。 2023-07-08 02:47 60阅读 0赞

利用队列，从前向后在队列中取数据时，此时向队列中插入数据，插在队列尾部；从后向前在队列中取数据时，此时若插入数据，插在队列头部。感觉这种思路比较容易想到。时间还能接受  
![时间还能接受。][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]

from collections import deque
    class Solution:
        def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
            res = []
            if not root:
                return res
            q = deque([root, ])
            count = 0          #记录层数
            status = True    #用于判断从队列中读取数据的顺序
            while q:
                res.append([])
                if status:
                    for _ in range(len(q)):  
                        node = q.popleft()   #从前向后在队列中取数据，则往队列中插入时，添加在队列尾部
                        res[count].append(node.val)
                        if node.left:
                            q.append(node.left)
                        if node.right:
                            q.append(node.right)
                else:
                    for _ in range(len(q)):
                        node = q.pop()    #从后向前在队列中取数据，则往队列中插入数据时，添加在队列头部
                        res[count].append(node.val)
                        if node.right:
                            q.insert(0, node.right)
                        if node.left:
                            q.insert(0, node.left)
                count += 1 
                status = not status
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200224203217140.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI=,size_16,color_FFFFFF,t_70