[AcWing]37. 树的子结构

输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。

我们规定空树不是任何树的子结构。

数据范围

每棵树的节点数量 [0,1000]。

样例：

树 B：

1
2
3

  8
 / \
9   2

返回 true，因为 B 是 A 的子结构。

算法思路

代码分为两个部分：

遍历树A中的所有非空节点R；
判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；

对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。

对于第二部分，我们同时从根节点开始遍历两棵子树：

如果树B中的节点为空，则表示当前分支是匹配的，返回true；
如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isPart(TreeNode* pA,TreeNode* pB){
        // 需要注意的是：必须先判断pB，否则遇到两棵一模一样的树，会返回false
        // 我曾写成这样，然后报错了。
        // if(!pA) return false;
        // if(!pB) return true;
        // 匹配成功的情况，B树已经遍历完了
        if(!pB) return true;
        // 匹配失败的情况(pB不为空)
        // B树相比A树更枝繁叶茂，或者A树和B树比较的节点值不同，则子结构匹配失败
        if(!pA || pA -> val != pB -> val) return false;
        // 如果A树和B树当前节点值相同，则继续匹配左右子树
        return isPart(pA -> left, pB -> left) && isPart(pA -> right, pB -> right);
    }

    bool hasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        //空树不是任何树的子结构。任何树也不是空树的子结构。
        if(!pRoot1 || !pRoot2) return false;
        // 如果是真的全匹配了，那么就是子结构
        // 需要区别于 => return isPart(pRoot1,pRoot2);
        // 上面这行是只要匹配错一个就直接错了，无容错空间。
        // 下面这行是有容错空间的，还可以执行下下行代码
        if(isPart(pRoot1,pRoot2)) return true;
        // 出现了一个节点不匹配，使得上面的出口未跳出
        // 说明需要进入A树的左右子树，继续进行匹配
        return hasSubtree(pRoot1 -> left, pRoot2) || hasSubtree(pRoot1 -> right, pRoot2);
    }
};

这里有个注意事项：代码注释已经写出，但这里抽出来再次解释

if(isPart(pRoot1,pRoot2)) return true;这行代码需要区别于 => return isPart(pRoot1,pRoot2);
return isPart(pRoot1,pRoot2);这行是只要匹配错一个就直接错了，无容错空间。
if(isPart(pRoot1,pRoot2)) return true;这行是有容错空间的，还可以执行if后面的代码。