题解 | #树的子结构#

#include <iostream>
using namespace std;

class Solution {
public:
    
    bool DoesTree1HasTree2(TreeNode* pRoot1, TreeNode* pRoot2){
        if(!pRoot2)  return true;
        else if(!pRoot1) return false;
        if( pRoot1 -> val == pRoot2 -> val){
            return DoesTree1HasTree2(pRoot1 -> left,pRoot2 -> left) && DoesTree1HasTree2(pRoot1 -> right,pRoot2 -> right); 
        }
        else return false;
    }
    
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2){
        bool res = false;
        if(!pRoot1 || !pRoot2){
            return false;
        }
        if(pRoot1 -> val == pRoot2 -> val){
            res = DoesTree1HasTree2(pRoot1,pRoot2);
        }
        if(!res && pRoot1 -> left){
            res = HasSubtree(pRoot1 -> left,pRoot2);
        }
        if(!res && pRoot1 -> right){
            res = HasSubtree(pRoot1 -> right,pRoot2);
        }
        return res;
    }

};

双递归法，主递归找到A的一个节点，如果这个节点能和B的根节点匹配上，那么就以这个节点为基准再开一个递归，来看A这个节点的左右子树是否能更B节点的左右子树相匹配。在次递归中，若pRoot2已经为null了，那么A的这个节点的这个子树就大于等于B，直接返回true，若pRoot2不为null而pRoo1为null的话，证明B比A中这个节点为根的子树要更大，所以返回false。然后判断他们两个的值是都相同。这样就能以A上的所有节点为跟节点，与B的所有节点进行一次比较了。