Ex26 树的子结构

解题思路

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

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

例如: 给定的树 A: 3 /
4 5 /
1 2 给定的树 B： 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

题目描述

结合代码，讲一下解题思路：

• 函数isSubStructure负责找到A、B有没有共同的结构；
• 函数is_sub_structure_core负责判断A、B是不是相同的树（在B是子树的情况下）。

代码

bool is_sub_structure_core (struct TreeNode *A, struct TreeNode *B);

bool
isSubStructure (struct TreeNode *A, struct TreeNode *B)
{
  return (A && B)
         && (is_sub_structure_core (A, B) || isSubStructure (A->left, B)
             || isSubStructure (A->right, B));
}

bool
is_sub_structure_core (struct TreeNode *A, struct TreeNode *B)
{
  if (!B)
    return true;
  if (!A || A->val != B->val)
    return false;
  return is_sub_structure_core (A->left, B->left)
         && is_sub_structure_core (A->right, B->right);
}

结果

执行结果：通过

执行用时：44 ms, 在所有 C 提交中击败了34.90%的用户

内存消耗：19.2 MB, 在所有 C 提交中击败了8.63%的用户

备注

这个case我是真不能理解啊：

A:[-1, 3, 2, 0], B:[], 结果为false。

空集不应该是所有集合的子集吗？