剑指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