二叉树-层序遍历

Posted on

题干 ： 返回二叉树层序遍历的结果 同时写出递归和非递归的写法

至于什么是层序遍历不用我赘述 其实就是用BFS的方法去搜索二叉树
同样 包含递归和非递归的写法 非递归写法需要用队列来实现

递归实现层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root :
            return []

        res=[]
     
        def traverse(node,level):
            if not node:
                return
            
            if len(res)==level:
                res.append([])   # 其实就是前序递归遍历加了一个判断
            res[level].append(node.val)
            traverse(node.left,level+1)
            traverse(node.right,level+1)
        traverse(root,0)
        return res

说实话 我不是很理解层序遍历的递归写法 感觉非递归的更好理解

非递归实现层序遍历

非常简单 头节点弹入队列后 每次弹出节点 把所有子节点放入队列末尾即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res=[]
        que=deque(root)
        while que:
            level=[]
            for _ in range(len(que)):
                cur=que.popleft()
                level.append(cur.val)
                if cur.left:
                   	que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
			res.append(level)
         return res