跟随carl代码随想录刷题
语言：python

---

101. 简单对称二叉树

题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。
😄示例1：

输入：root = [1,2,2,3,4,4,3]
输出：true
😭示例2：

输入：root = [1,2,2,null,3,null,3]
输出：false

题目分析

• 左右节点为空：对称，return true

• 左节点为空，右节点不为空：不对称，return false

• 左节点不为空，右节点为空：不对称，return false

• 左右节点都不为空：比较节点数值，不相同return false

• 否则：return true

下一步

• 比较二叉树外侧是否对称：传入的是左节点的左孩子，右节点的右孩子。
• 比较内测是否对称，传入左节点的右孩子，右节点的左孩子。
• 如果左右都对称就返回true ，有一侧不对称就返回false 。

完整代码如下

递归法

# 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
        return self.compare(root.left, root.right)

    def compare(self, 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 = self.compare(left.left, right.right)  # 左子树的左节点，右子树的右节点
        inside = self.compare(left.right, right.left)  # 左子树的右节点，右子树的左节点
        isSame = outside and inside
        return isSame
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

使用队列

使用队列来对比两个树（根节点的左右子树）是否相互翻转

# 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
        que = collections.deque()
        que.append(root.left)
        que.append(root.right)

        while que:
            # 每次从队列中连续取两个值进行下述判断
            leftNode = que.popleft()
            rightNode = que.popleft()
            if not leftNode and not rightNode:  # 左节点为空，右节点为空，则对称
                continue
            if not leftNode or not rightNode or leftNode.val != rightNode.val:
                return False
            
            que.append(leftNode.left)  # 左节点的左孩子
            que.append(rightNode.right)  # 右节点的右孩子
            que.append(leftNode.right)  # 左节点的右孩子
            que.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
23
24
25
26
27
28

使用栈

# 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
        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
20
21
22
23
24
25

100. 相同的树

题目：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

完整代码如下

# 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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:  # 都为空
            return True
        elif not p or not q:  # 一个为空，一个不为空
            return False
        elif p.val != q.val:  # 都不为空，但是值不相等
            return False
        else:  # 都不为空，值也相等，那就进行递归
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

572. 另一棵树的子树

题目：给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

题目分析

先明确一下，什么是子树？
如果包含根节点在内，那子树就是整棵树，这个概念要理清。也就是说：

下面这个图不是子树！！！不是子树！！！不是子树！！！

判断是否为子树，分为三种情况：

1. 树1的根节点 与 树2的根节点 进行相同树函数判断，如果相同，就返回True
2. 既然走到第二步了，就说明两个树的根节点不相同。因此往下判断：如果：
   • 树1的节点的右节点 与 树2的节点 进行子树函数判断
   • 树1的节点的左节点 与 树2的节点 进行子树函数判断
   • 树1的节点 与 树2的节点 进行相同树函数判断

完整代码如下

# 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 isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if root == None and subRoot == None:
            return True
        if root == None or subRoot == None:
            return False
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) or self.isSameTree(root, subRoot)

        
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:  # 都为空
            return True
        elif not p or not q:  # 一个为空，一个不为空
            return False
        elif p.val != q.val:  # 都不为空，但是值不相等
            return False
        else:  # 都不为空，值也相等，那就进行递归
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24