剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。

DFS+前序

思路

若B为A的子结构，则子结构的根节点可能为树A的任意一个节点，因此判断B是否为树A的子结构，需要完成如下2步工作：

1. 先序遍历树A中每个节点;（isSubStructure(A,B)）
2. 判断以为根节点的子树是否包含树B。（recur(A,B)）;

   算法

   树A的根节点记作节点A，树B的根节点记作节点B

**recur(A,B)**:

1. 终止条件：
   1. 当节点B为空，说明树B已匹配完成（越过叶子节点），true
   2. 当节点A为空：说明树A越过叶子节点，false
   3. 当节点A与B值不同：false;
2. 返回值：
   1. 判断A和B的左子节点是否相等，即recur(A.left,B.left);
   2. 判断A和B的右子节点是否相等，即recur(A.right,B.right);

isSubStructure(A, B) 函数：

1. 特例处理：当树A为空或树B为空时，false;
2. 返回值：若树B为树A的子结构，则必然满足如下三种情况之一，以||连接
   1. 以节点A为根节点的子树包含树B，对应recur(A,B);
   2. 树B是树A的左子树的子结构，对应isSubStructure(A.left, B)
   3. 树B是树A的右子树的子结构，对应isSubStructure(A.right, B)

      以上a.b.c实质为先序遍历

实现（递归实现）

bool recur(TreeNode*,TreeNode*);
bool isSubStructure(TreeNode* A,TreeNode* B){
    return bool(A && B) 
        && (recur(A,B) || isSubStructure(A->left,B) || isSubStructure(A->right,B);
}
bool recur(TreeNode* A,TreeNode* B){
    //用以判断以A为根节点的树是否包含树B
    if(!B) return true;
    if(!A || A->val!=B->val) return false;
    return recur(A.left,B.left) && recur(A.right,B.right);
}

实现（非递归BFS实现）

bool isSubStructure(TreeNode* A,TreeNode* B){
    if(!A || !B) return false;
    queue<TreeNode*> qu;
    qu.push(A);
    while(!qu.empty()){
        auto curNode=qu.front();
        qu.pop();
        if(bfs(curNode,B)){
            return true;
        }
        if(curNode->left) qu.push(curNode->left);
        if(curNode->right) qu.push(curNode->right);
    }
    return false;
}
bool bfs(TreeNode* A,TreeNode* B){
    queue<TreeNode*> quA,quB;
    quA.push(A);
    quB.push(B);
    while(!quA.empty() || !quB.empty()){
        auto curA=quA.front();
        auto curB=quB.front();
        quA.pop();
        quB.pop();
        if(!curB) continue;
        if(!curA || curA->val!=curB->val) return false;
        quA.push(curA->left);
        quA.push(curA->right);
        quB.push(curB->left);
        quB.push(curB->right);
    }
    return true;
}

复杂度分析

• 时间复杂度: ,先序遍历A树为O(M)，每次A树遍历都需要调用recur(A,B),占用O(N)
• 空间复杂度:，当M<=N时，遍历树A与递归判断总深度为M；若M>N，最差情况下遍历至A的叶子节点，故总深度为M；

BFS

思路

算法

实现

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分