26-树的子结构

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

method

双重递归

bool dfs(TreeNode *A, TreeNode *B) {    // 判断相同的树
    if (!B) return true;
    if (!A || A->val != B->val) return false;
    return dfs(A->left, B->left) && dfs(A->right, B->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
    if (!A || !B) return false;
    bool b1 = dfs(A, B);    // 当前节点找
    bool b2 = isSubStructure(A->left, B);   // 左子树找
    bool b3 = isSubStructure(A->right, B);  // 右子树找
    return b1 || b2 || b3;
}