题解 | #树的子结构#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param pRoot1 TreeNode类
# @param pRoot2 TreeNode类
# @return bool布尔型
#
class Solution:
    def preorder(self, pRoot: TreeNode) -> List:
        if pRoot == None:
            return []        
        li = []
        li.append(pRoot.val)
        if pRoot.left:
            li.extend(self.preorder(pRoot.left))
        if pRoot.right:
            li.extend(self.preorder(pRoot.right))
        return li

    def inorder(self, pRoot: TreeNode) -> List:
        if pRoot == None:
            return []
        li = []
        if pRoot.left:
            li.extend(self.inorder(pRoot.left))
        li.append(pRoot.val)
        if pRoot.right:
            li.extend(self.inorder(pRoot.right))
        return li

    def traversal_cmp(self, A:List, B:List) -> bool:
        i,j = 0, 0
        flag = False
        while i<len(A) and j<len(B):
            if A[i] == B[j]:
                i += 1
                j += 1
                if j >= len(B):
                    flag = True
                    break
            else:
                i += 1
        return flag

    def HasSubtree(self, pRoot1: TreeNode, pRoot2: TreeNode) -> bool:
        # write code here
        A_pre_list = self.preorder(pRoot1) # 前序遍历A树
        B_pre_list = self.preorder(pRoot2) # 前序遍历B树
        # print(A_pre_list,B_pre_list)

        A_in_list = self.inorder(pRoot1) # 中序遍历A树
        B_in_list = self.inorder(pRoot2) # 中序遍历B树
        # print(A_in_list,B_in_list)
        
        ans = self.traversal_cmp(A_pre_list,B_pre_list) and self.traversal_cmp(A_in_list, B_in_list)

        return ans

我的思路如下：

1. 对于二叉树的前序遍历、中序遍历、后序遍历序列，只要知道任意其中两个，就可以还原出第三个遍历序列。比如，已知前序序列、中序序列，那么就能重建该二叉树。因此，可以认为在已知前序遍历、中序遍历序列的情况下，就能够唯一确定一棵二叉树。
2. 因此，对于待比较的A树和B树，分别通过前序遍历、中序遍历保存下它们的节点，存储为A_pre_list、B_pre_list列表，以及A_in_list和B_in_list列表。

• 条件一：如果B树的前序遍历序列是A树的前序遍历序列的子序列(要求保证前后的顺序不变，但可以是跳跃的)，比如对于题目中的样例，A树的前序遍历为[8, 8, 9, 2, 4, 7, 7]。B树的前序遍历为[8, 9, 2]。
• 条件二：如果B树的中序遍历序列是A树的中序遍历序列的子序列(要求保证前后的顺序不变，但可以是跳跃的)，比如对于题目中的样例，A树的中序遍历为[9, 8, 4, 2, 7, 8, 7]。B树的中序遍历为[9, 8, 2]。

3. 当条件一和条件二同时满足时，我们认为B树是A树的子结构。

• 时间复杂度：max(O(m), O(n))，其中m为二叉树A的节点数，n为二叉树B的节点数，所有的节点都会被遍历一遍。