代码随想录算法训练营第15日 | 层序遍历 226.翻转二叉树 101.对称二叉树 2_代码随想录bfs算法

系列文章目录

代码随想录——二叉树篇

---

---

层序遍历

理论基础 & 代码模板

队列实现二叉树广度优先遍历

BFS的算法模板

queue = deque()
queue.append(root)
while queue:
    size = len(queue)
    for i in range(size):
        curr = queue.popleft()
        queue.append(curr.children)
1
2
3
4
5
6
7

自己稍微解释一下这个算法模板，它是用队列去模拟广度优先搜索

首先，queue把root结点加进来，然后popleft出，用一个curr 去代表目前pop出的元素； 然后把curr的子结点全部加进队列；
然后继续进入循环，size此时是队列的长度也是这一层结点的个数，然后我们只popleft出该层长度个结点，
因为我们每pop出一个元素，就需要把它的孩子加入队列，此时队列是有两层结点元素的，所以需要一个size参数去限定我们只出队这一层的结点。
然后继续把它们的子结点入队，如此循环往复…

102.二叉树的层序遍历

# 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 = []
        queue = deque()
        queue.append(root)
        while queue:
            layer = []
            length = len(queue)  
            for i in range(length):
                curr = queue.popleft()
                layer.append(curr.val)
                if curr.left: queue.append(curr.left)
                if curr.right:queue.append(curr.right)
            res.append(layer)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
1
2

while queue控制整个队列不空的话，就是树没有遍历完全
layer 和 length 参数，是在每层遍历结束后 都会更新的参数
而for i in range(length): 后面的操作是在每层之内，操作的逻辑

226.翻转二叉树

首先要明确，这道题采用什么方法去做
对二叉树的遍历有递归的方法，也有用栈去模拟的方法（根入栈，然后弹出，然后右孩子入栈，左孩子入栈，然后弹出）

在这里翻转二叉树，如果用递归的方法很好写，但是要明确用前序，中序，还是后序

对于前序后序，交换左右结点这个操作在递归的前和后，不会出现问题

但是如果中序的话，需要注意，左边子树操作完了，又把左子树换到了右边，此时如果再操作右子树就重复操作了，还是要操作左子树，只不过此时的左子树是原本的右子树

递归法的代码

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root: return            #防止了进入函数的结点是空的情况
        root.left, root.right = root.right, root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
1
2
3
4
5
6

去模拟操作的方法（迭代法）也很简单，分为dfs(前序)，和bfs的方法

迭代法（dfs）

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        st = []
        st.append(root)
        while st:
            node = st.pop()
            node.left, node.right = node.right, node.left #中
            if node.right:
                st.append(node.right) #右
            if node.left:
                st.append(node.left) #左
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14

迭代法（bfs）

import collections
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        queue = collections.deque() #使用deque()
        if root:
            queue.append(root)
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                node.left, node.right = node.right, node.left #节点处理
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

101. 对称二叉树

这道题卡哥说要明白两个关键点：
1.二叉树是否对称，要看它翻转之后，还是不是那棵树
2.就是要明确遍历的方式是什么，是前序，中序，还是后序

递归法

在写compare(left, right) 函数，要明确的一点，这道题只能用后序遍历，也就是判断左子树是对称的，右子树也是对称的，之后，才能判断这个树是对称的

感觉就是，判断左子树，判断右子树，然后把and的结果传递给根结点代表的这个子树，然后一点一点累积到root

# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        def compare(left, right):
            if left == None and right != None: return False
            elif left != None and right == None: return False
            elif left == None and right == None: return True
            elif left.val != right.val: return False

            # 此时是左右结点都不为空，然后值相等的情况
            outside = compare(left.left, right.right)
            inside = compare(left.right, right.left)
            isSame = outside and inside
            return isSame
        
        return compare(root.left, root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

迭代法： 使用队列

import collections
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        queue = collections.deque()
        queue.append(root.left) #将左子树头结点加入队列
        queue.append(root.right) #将右子树头结点加入队列
        while queue: #接下来就要判断这这两个树是否相互翻转
            leftNode = queue.popleft()
            rightNode = queue.popleft()
            if not leftNode and not rightNode: #左节点为空、右节点为空，此时说明是对称的
                continue
            
            #左右一个节点不为空，或者都不为空但数值不相同，返回false
            if not leftNode or not rightNode or leftNode.val != rightNode.val:
                return False
            queue.append(leftNode.left) #加入左节点左孩子
            queue.append(rightNode.right) #加入右节点右孩子
            queue.append(leftNode.right) #加入左节点右孩子
            queue.append(rightNode.left) #加入右节点左孩子
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

迭代法：使用栈

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        st = [] #这里改成了栈
        st.append(root.left)
        st.append(root.right)
        while st:
            leftNode = st.pop()
            rightNode = st.pop()
            if not leftNode and not rightNode:
                continue
            if not leftNode or not rightNode or leftNode.val != rightNode.val:
                return False
            st.append(leftNode.left)
            st.append(rightNode.right)
            st.append(leftNode.right)
            st.append(rightNode.left)
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19