leetcode [面试题26] 树的子结构

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

来自题解:

注意判断顺序。

class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:
        res = False
        if A is not None and B is not None:
            if A.val == B.val:
                res = self.helper(A,B)
            if not res:
                res = self.isSubStructure(A.left, B)
            if not res:
                res = self.isSubStructure(A.right, B)
        return res
    
    def helper(self, A, B):
        if B is None:
            return True
        if A is None:
            return False
        if A.val != B.val:
            return False
        return self.helper(A.left, B.left) and self.helper(A.right, B.right)