描述

这是一篇面对初级coder的题解。
知识点：链表 递归 DFS
难度：三星

题解

题目：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

考察树的基础知识与递归的思路，深度优先搜索。

方法一：递归求解

思路：双重递归

递归一：递归判断子树中有无子结构

对应HasSubtree（）

递归二：判断当前树根是否对应子结构

对应issame（）函数

class Solution {
public:
    bool IsSame(TreeNode* pRoot1, TreeNode* pRoot2)//递归判断是否是子结构
    {
        bool left=true,right=true;//左右是否相同 空的时候默认均匹配
        if(!pRoot1||pRoot1->val!=pRoot2->val) //判断头节点
            return false;
        if(pRoot2->left)//递归判断左侧节点，需要判断子结构是否为空
            left=IsSame(pRoot1->left, pRoot2->left);
        if(pRoot2->right)//递归判断右侧节点，需要判断子结构是否为空
            right=IsSame(pRoot1->right, pRoot2->right);
        return left&&right;//左右节点都相同才是子结构
    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) //递归判断子树里有无所求子结构
    {
        if(!pRoot2||!pRoot1) //边界条件 空树返回false
            return false;
        if(IsSame(pRoot1, pRoot2))//递归判断是否是子结构
            return true;
        if(HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2))//递归判断左右节点有无子结构
            return true;
        else
            return false;
    }
};

复杂度分析：

时间复杂度 O(MN)： 其中 M,N 分别为树 A 和 树 B 的节点数量；先序遍历树 A 占用 O(M) ，每次调用IsSame(TreeNode* pRoot1, TreeNode* pRoot2)判断占用 O(N)。
空间复杂度 O(M) ： 当树 A 和树 B 都退化为链表时，递归调用深度最大。当 M ≤N 时，遍历树 A 与递归判断的总递归深度为 M ；当 M>N时，最差情况为遍历至树 A叶子节点，此时总递归深度为 M。

运行时间11ms 占用内存600KB

总结

递归的解法在树的解题中有广泛应用：

如下动图展示了深度优先搜索的递归算法：

if(!root) 
    return true/false;
if(!root->left) 
    return true/false/递归函数;
if(!root->right) 
    return true/false/递归函数;

if(!p && !q)
    return true/false;
if(!p || !q)
    return true/false;