剑指 Offer 26. 树的子结构

题目描述

输入两棵二叉树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

链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof

解题思路

很容易想到使用dfs解决问题。一种比较复杂的匹配方式是这样的：
给定的树 A:

     10
    / \
   12   6
  / \    \
 8   3   11

给定的树 B：

     10
    / \
   12   6
  /
 8

因此，我们从遍历到的最终子树来看，可以根据A和B是否存在、A和B的val是否相等确定返回值。
关键点在于：

l_result = self.pattern(A.left, B.left)
r_result = self.pattern(A.right, B.right)
return l_result and r_result

解题代码

class Solution:
    # 匹配的原则是是否一旦有节点不合适，就返回一个False
    def pattern(self, A: TreeNode, B: TreeNode) -> bool:
        # 主要比较的是B的结构是否在A中存在，如果B不存在，就失去了比较的必要
        if not B:
            return True
        # B中的节点在A中不存在
        elif not A and B:
            return False
        # B和A都存在，比较B和A的val是否相同 
        elif A and B:
            if A.val != B.val:
                return False
            if A.val == B.val and (not B.left and not B.right):
                return True
        # 后序遍历，左结果和右结果相与
        l_result = self.pattern(A.left, B.left)
        r_result = self.pattern(A.right, B.right)
        return l_result and r_result

    def dfs(self, A: TreeNode, B: TreeNode):
        if not A:
            return
        if not self.result:
            self.result |= self.pattern(A, B)
            self.dfs(A.left, B)
            self.dfs(A.right, B)

    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        if not B:
            return False
        self.result = False
        self.dfs(A, B)
        return self.result

执行结果

执行结果：通过
执行用时：96 ms, 在所有 Python3 提交中击败了69.99%的用户
内存消耗：19.3 MB, 在所有 Python3 提交中击败了34.50%的用户