剑指Offer26-树的子结构

剑指Offer26-树的子结构

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

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

例如:

给定的树 A:


    3

   / \

  4   5

 / \

1   2

给定的树 B:


  4

 /

1

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

示例 1:


输入:A = [1,2,3], B = [3,1]

输出:false

示例 2:


输入:A = [3,4,5,1,2], B = [4,1]

输出:true

限制:


0 <= 节点个数 <= 10000

来源:力扣(LeetCode)

链接:力扣

一解

  • 先序遍历“树A”中的每一个“节点K”

  • 判断“以K为根节点的树”是否包含“树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:

        # 判断“以K为根节点的树”是否包含“树B”

        def recur(A, B):

            if not B: return True

            if not A or A.val != B.val: return False

            return recur(A.left, B.left) and recur(A.right, B.right)

        # 先序遍历树 A  

        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))

设M, N为“树A”和“树B”的节点数量

  • 时间复杂度O(MN):先序遍历“A树”,占用O(M),每次调用recur(A, B),占用O(M)

  • 空间复杂度O(M):假设A,B是链表(链表的递归遍历深度最大),当M>N时,需要完整遍历A,占用空间O(M),当M<=N时,遍历完A,如果B还存在子节点,说明不匹配,无需继续遍历,遍历深度为M