题目描述 牛客网

• 输入两颗二叉树 A 和 B，判断 B 是不是 A 的子结构

题目解读

• 剑指Offer 149

代码

class Solution {
public:
    bool Equal(int a, int b){
        if(a-b == 0){
            return true;
        }
        else{
            return false;
        }
    }

    bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        if(!pRoot2){
            return true;
        }

        if(!pRoot1){
            return false;
        }

        if(!Equal(pRoot1->val, pRoot2->val)){
            return false;
        }

        return DoesTree1HaveTree2(pRoot1->left, pRoot2->left) && DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
    }

    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result = false;

        if(pRoot1 && pRoot2){
            if(Equal(pRoot1->val, pRoot2->val)){
                result = DoesTree1HaveTree2(pRoot1, pRoot2);
            }

            if(!result){
                result = HasSubtree(pRoot1->left, pRoot2);
            }

            if(!result){
                result = HasSubtree(pRoot1->right, pRoot2);
            }
        }

        return result;
    }
};

总结展望

• 二叉树的题目需要增强，目前比较薄弱