剑指offer-树的子结构

本文为剑指 offer 系列第十九篇。
主要知识点为树，主要是对树进行相关的遍历，对树的相似性进行判断。

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路

依次遍历A的所有节点，然后来判断当前节点所在的部分是不是和B的结构一致就可以。可以直接使用递归。

解题代码

/*
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)
    {
        if(!pRoot2 || !pRoot1) return false;
        if(pRoot1->val == pRoot2->val && helper(pRoot1,pRoot2)){
            return true;
        }else{
            return HasSubtree(pRoot1->left,pRoot2)||HasSubtree(pRoot1->right,pRoot2);
        }
    }
    bool helper(TreeNode* pRoot1,TreeNode* pRoot2){
        if(!pRoot2) return true;
        if(!pRoot1) return false;
        if(pRoot1->val == pRoot2->val){
            return helper(pRoot1->left,pRoot2->left) && helper(pRoot1->right,pRoot2->right);
        }else{
            return false;
        }
    }
};

设A、B的节点数分别为m、n，最坏时间复杂度为O(m*n)，辅助空间复杂度为O(h)，h是A的高度。A的每个候选节点都可能重新匹配B。
以上，本题结束！