汇芳书院

专注计算机视觉、机器学习、分布式计算等领域, 兼聊投资、写作、生活

0%

之字型层序打印二叉树

发表于 更新于 分类于 Valine：
本文字数： 1.5k 阅读时长 ≈ 1 分钟

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

结果集双端队列，避免翻转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        queue = collections.deque()
        queue.append(root)
        flag = False
        while queue:
            length = len(queue)
            # 结果集也用双端队列，省去一次翻转动作
            result = collections.deque()
            for i in range(length):
                p = queue.popleft()
                if flag:
                    result.appendleft(p.val)
                else:
                    result.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right) 
            ans.append(list(result))
            flag = not flag
        return ans




双端队列 奇偶层逻辑分离

可以实际画一个双端队列感受一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        ans = []
        if not root:
            return ans
        queue = collections.deque()
        queue.append(root)
        while queue:
            # 处理奇数层 从左向右打印 从左向右添加下层节点
            length = len(queue)
            result = list()
            for i in range(length):
                p = queue.popleft()
                result.append(p.val)
                if p.left:
                    queue.append(p.left)
                if p.right:
                    queue.append(p.right) 
            ans.append(list(result))
            if not queue:
                break
            
            # 处理偶数层 从右向左打印 从右向左添加下层节点
            length = len(queue)
            result = list()
            for i in range(length):
                p = queue.pop()
                result.append(p.val)
                if p.right:
                    queue.appendleft(p.right) 
                if p.left:
                    queue.appendleft(p.left)
            ans.append(list(result))
        return ans




坚持原创分享，您的支持将鼓励我继续创作

欢迎关注我的其它发布渠道

------------- 本文结束,感谢阅读 如有问题可留言交流 -------------