leetcode-102

发表于
字数统计: 553字 | 阅读时长 ≈ 2分钟

102. 二叉树的层序遍历

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

代码及解析：

将同一层的节点存到一个临时数组中，访问完同一层的所有节点，就将该临时数组添加到结果res数组中，利用队列每访问一个节点，将其pop掉，然后将该节点的左右节点推入队列，直到队列为空，返回结果res结束。

代码：

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
# 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]]:
        if not root:
            return []
        res=[]
        deque=[root]
        while deque:
            tmp = []
            node = []
            while deque:
                que=deque.pop(0)
                tmp.append(que.val)
                if que.left:
                    node.append(que.left)
                if que.right:
                    node.append(que.right)
            deque.extend(node)
            res.append(tmp) 
        return res

注释：

1
2
3
4
5
extend与append的区别：
    两者作用差不多，都是添加元素至数组中，两者区别在于，比如添加一个数组，前者是按顺序在数组最后一个一个的添加进去，而后者是直接将整个数组添加进去，
比如:a=[1],b=[2,3]
extend:a=[1,2,3]
append:a=[1,[2,3]]

举一反三：

leetcode-107：与上述题目一样，只是将结果反向输出即可

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        deque=[root]
        res=[]
        while deque:
            temp=[]
            extend=[]
            while deque:
                que=deque.pop(0)
                temp.append(que.val)
                if que.left:
                    extend.append(que.left)
                if que.right:
                    extend.append(que.right)
            deque.extend(extend)
            res.append(temp)
        return res[::-1] #将数组反向顺序返回即可

leetcode-104：求二叉树的最大深度，利用层序遍历，每遍历一层深度+1

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        max=0
        if not root:
            return 0
        deque=[root]
        while deque:
            tmp = [] #存储每层的节点
            node = []
            while deque:
                que=deque.pop(0)
                tmp.append(que.val)
                if que.left:
                    node.append(que.left)
                if que.right:
                    node.append(que.right)
            if tmp:
                max+=1 #若此层不为空，深度+1
            deque.extend(node)
        
        return max

写在最后：

如果您有任何不明白，或描述上述有问题，请在下方留言。

hey!baby,站住，点它!