python每日一题【剑指 Offer 26. 树的子结构】

day23-2022.11.19

题目信息来源

作者：Krahets

链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm

来源：力扣（LeetCode）

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

 	 3
	/ \
   4   5
  / \
 1   2
1
2
3
4
5

给定的树 B：

	4 
  /
 1
1
2
3

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

输入：A = [1,2,3], B = [3,1]
输出：false

输入：A = [3,4,5,1,2], B = [4,1]
输出：true
1
2
3
4
5

限制：0 <= 节点个数 <= 10000

题解：个人版，队列方法

可能是广度遍历的方法。我的代码可以看到有很多重复，结构相似的代码段，之后看看题解考虑一下怎么优化。现在先考虑能不能用递归的方式

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not B:return False       # 空树不是任何树的子结构
        # 考虑了一下，可能是三个队列，一个是A的所有节点队列遍历，一个是B的所有队列，一个是检查A的时候单独的队列
        aQueue = [A]
        check_sub = False
        while aQueue:
            # 检查a队列有无和b队列对上的
            aNode = aQueue.pop(0)
            # 如果对不上考虑下一个节点
            if aNode.left!=None:aQueue.append(aNode.left)
            if aNode.right!=None:aQueue.append(aNode.right)
            # 如果对上，就需要检查结构，遍历b的结构
            if aNode.val==B.val:
                # 初始化b的遍历结构和a对应的子结构
                aSub, bSub = [aNode], [B]
                while bSub:
                    a_node, b_node = aSub.pop(0), bSub.pop(0)
                    # 如果pop的值相等，则可以考虑看看树的下一层的情况
                    if b_node.val==a_node.val:
                        # left都不为空，暂时结构上是正确的
                        if b_node.left!=None and a_node.left!=None:
                            bSub.append(b_node.left)
                            aSub.append(a_node.left)
                            check_sub = True
                        # b不为空，a为空结构上错误
                        elif b_node.left!=None and a_node.left==None:
                            check_sub = False
                            break
                        # a和b都为空，结构上是正确的。
                        # 其实还有一种情况:b为空，a不为空，这个我也不知道怎么处理其实，但似乎测试里没有这种情况，或者就是False
                        elif b_node.left==None:check_sub = True
                        if b_node.right!=None and a_node.right!=None:
                            bSub.append(b_node.right)
                            aSub.append(a_node.right)
                            check_sub = True
                        elif b_node.right!=None and a_node.right==None:
                            check_sub = False
                            break
                        elif b_node.right==None:check_sub = True
                    else:
                        check_sub = False
                        break
        return check_sub
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
46
47
48
49
50
51

题解：个人方法，递归版本

这个很像之前的【矩阵中的路径】那道题，就是数据结构变了一下，如果广度就要两层遍历，深度就需要一层遍历加递归。

这里官方题解的解释更清楚，为啥需要两层遍历：

链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dsbng/

若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 A 的子结构，需完成以下两步工作：

1. 先序遍历树 A 中的每个节点 $n_A$ ；（对应函数 isSubStructure(A, B)）
2. 判断树 A 中 以 $n_A$ 为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not B:return False       # 空树不是任何树的子结构
        # 递归参数：A和B的left或者right Node
        # 递归获得参数有多少种可能性，分别返回什么参数。首先希望传递的参数是出现子树可能性的时候的递归
        def checkSubTree(a_node, b_node):
            # 检查 aNode 的值和 bNode 的值是否相等
            if a_node==None and b_node!=None:return False
            elif b_node==None:return True
            if a_node.val!=b_node.val:return False
            return checkSubTree(a_node.left, b_node.left) and checkSubTree(a_node.right, b_node.right)

        aQueue = [A]
        while aQueue:
            # 检查a队列有无和b队列对上的
            aNode = aQueue.pop(0)
            # 如果对不上考虑下一个节点
            if aNode.left!=None:aQueue.append(aNode.left)
            if aNode.right!=None:aQueue.append(aNode.right)
            # 如果对上，就需要检查结构，遍历b的结构
            if aNode.val==B.val:
                check_sub = checkSubTree(aNode.right, B.right) and checkSubTree(aNode.left, B.left)           
                if check_sub==True:return True
                else:continue
        return False
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

看到最后官方题解是基于递归版本，在第一层遍历部分，用来递归来解决。

链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dsbng/

返回值： 若树 B 是树 A 的子结构，则必满足以下三种情况之一，因此用或 || 连接；

• 以 节点 A 为根节点的子树 包含树 B ，对应 recur(A, B)；
• 树 B 是 树 A 左子树 的子结构，对应 isSubStructure(A.left, B)；
• 树 B 是 树 A 右子树 的子结构，对应 isSubStructure(A.right, B)；

可以尝试在我的基础上从这个思路上优化，但特殊情况我可能现在提前 return，需要注意的是，这里还要加入 not A ，中间是 or 连接。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not B or not A:return False       # 空树不是任何树的子结构
        # 递归参数：A和B的left或者right Node
        # 递归获得参数有多少种可能性，分别返回什么参数。首先希望传递的参数是出现子树可能性的时候的递归
        def checkSubTree(a_node, b_node):
            # 检查 aNode 的值和 bNode 的值是否相等
            if a_node==None and b_node!=None:return False
            elif b_node==None:return True
            if a_node.val!=b_node.val:return False
            return checkSubTree(a_node.left, b_node.left) and checkSubTree(a_node.right, b_node.right)
        return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B) or checkSubTree(A, B)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19