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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一开始没注意子结构和子树的区别

# 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, s: TreeNode, t: TreeNode) -> bool:
        if not s or not t:return False
        def isIdentical(s,t):
            if not s and not t:return True
            return s and t and s.val==t.val
                     and isIdentical(s.left,t.left) and isIdentical(s.right,t.right)
        if not s and not t:return True
        if not s and t:return False
        return isIdentical(s,t) or self.isSubStructure(s.left,t) or self.isSubStructure(s.right,t)

 子结构和子树不一样，子结构只要满足t树遍历完 结构和值与s中的某部分相同就算 [1]是 [1,2,3] 的子结构，但[1]不是[1,2,3]的子树

# 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, s: TreeNode, t: TreeNode) -> bool:
        if not s or not t:return False
        def isIdentical(s,t):
            if not t:return True
            if not s:return False
            return s.val==t.val and isIdentical(s.left,t.left) and isIdentical(s.right,t.right)
        return isIdentical(s,t) or self.isSubStructure(s.left,t) or self.isSubStructure(s.right,t)