力扣-剑指 Offer 26. 树的子结构（C++）- 递归+深度遍历+有价值

た入场券 2022-09-09 09:47 161阅读 0赞

题目链接：[https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/][https_leetcode-cn.com_problems_shu-de-zi-jie-gou-lcof]  
题目如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_19_color_FFFFFF_t_70_g_se_x_16]

/**
     * 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 isSubStructure(TreeNode* A, TreeNode* B) {
        
        	//目的是找到两个是节点的情况，然后进入另一个函数判断是不是当前节点
            if(B==NULL||A==NULL) return false;
    
            if(issub(A,B)) return true;
            else return isSubStructure(A->left,B)||isSubStructure(A->right,B);//递归遍历A树的所有点，去匹配B树。注意：这里是||，即只要满足一个即可
        }
    
        bool issub(TreeNode* A,TreeNode* B){
        //用来判断第二个点中是否存在与之对应的在A中的点
    
            // if(A==NULL&&B==NULL) return true;
            if(B==NULL) return true;
    
            if(A==NULL&&B!=NULL) return false;
            if(A!=NULL&&B==NULL) return false;
            if(A->val!=B->val) return false;
    
            return issub(A->left,B->left)&&issub(A->right,B->right);//注意：这里是&&，需要两个都满足才行
        }
    };

[https_leetcode-cn.com_problems_shu-de-zi-jie-gou-lcof]: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBASkluZ2xlczEyMw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/57e849c690bd4b4abdd3555ff653f8fc.png