题解 | #树的子结构#

第十四题 比较一个树 是否为另一个树的子树

相对13 题比较简单

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
        // 当pRoot1 为空 则递归返回false
        // 当pRoot2 为空 直接返回false
        if(pRoot1==NULL || pRoot2==NULL)
            return false;
        
        // 先序遍历 访问值的功能修改为 比较是不是和pRoot2的根一样
        // 当看到 和pRoot2一样的根的时候 开始比较是不是会和pRoot2一样
        // （比较的函数isequal通过同步遍历pRoot2和pRoot的子树）如果不是 就返回原函数继续向下遍历
        bool ret_ans=false;
        
        // 如果当前 val相等 就去判断是否相等
        if(pRoot1->val == pRoot2->val)
        {
            ret_ans = isequal(pRoot1, pRoot2);
            // 如果得到答案是true 就直接返回true 答案是false 就带代表当前点不是 就继续递归
            if(ret_ans == true)
                return ret_ans;
        }
        
        // 先序遍历pRoot1
        ret_ans = HasSubtree(pRoot1->left,pRoot2);
        // 如果得到答案是true 就直接返回true 答案是false 就带代表当前点不是 就继续递归
        if(ret_ans==true)
            return true;
        ret_ans = HasSubtree(pRoot1->right,pRoot2);
        return ret_ans;
    }
    
    // （比较的函数isequal通过同步遍历pRoot2和pRoot的子树）如果不是 就返回原函数继续向下遍历
    bool isequal(TreeNode* pRoot1, TreeNode* pRoot2){
        // 如果出现了值不一样 直接返回false
        if(pRoot1->val!=pRoot2->val)
            return false;
        bool ret_ans =true;
        
        // 两种情况 原树没有左（右）子树 但是pRoot2 还有则说明肯定不匹配 return false
        if(pRoot1->left ==NULL && pRoot2->left!=NULL || pRoot1->right == NULL && pRoot2->right!=NULL)
            return false;
        
        // 先序遍历的
        // 先看左边 右边同理
        if(pRoot1->left!=NULL)
        {
            // 如果pRoot2 左边还有 就要匹配
            if(pRoot2->left!=NULL)
                // 这边递归调用，让两棵树同步递归
                ret_ans = isequal(pRoot1->left, pRoot2->left);
            // 如果pRoot2 左边没了 则不用匹配 此时左边肯定对
            else
                ret_ans=true;
        }
        
        // 如果左边已经出错了 直接return false
        if(ret_ans==false)
            return false;
        
        // 同理检查右边
        if(pRoot1->right!=NULL)
        {
            if(pRoot2->right!=NULL)
                ret_ans = isequal(pRoot1->right, pRoot2->right);
            else
                ret_ans=true;
        }
        return ret_ans;
    }
};