[二叉树] 树的子结构

题目描述

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

解题思路：
前序遍历A树，寻找A树中和B树根节点相同的节点。
A. 若A树的节点和B树的根节点相同，则A，B两树同时以当前节点开始前序遍历，比较A，B树中节点是否相同，若不相同则退出当前的遍历，并返回当前结果。
B. 若A树的节点和B树的根节点不相同，或A中返回结果为false，继续遍历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 isSameTree(TreeNode* x, TreeNode* y)
    {
        bool res = false;
        if(y == NULL) return true;//y=NULL，证明B树中所有节点已经比较完了，并且均与A树节点相同
        if(x == NULL) return false;//B树节点还没有比较完，A树节点已经比较完了。
        
        if(x->val == y->val)
        {
            res = isSameTree(x->left,y->left);
            if(res)
            {
                res = isSameTree(x->right,y->right);
            }
        }
        return res;
    }
    bool HasSubtree(TreeNode*x, TreeNode* y)
    {
        bool res = false;
        if(x==NULL || y==NULL)
            return false;
        if(x->val == y->val)//在A树中找到与B树根节点相同的节点
        {
            res = isSameTree(x,y);
        }
        if(!res)//没有找到相同的节点或B树此时不是A树种以当前节点为根节点树的子树
            res = HasSubtree(x->left,y);
        if(!res)
            res = HasSubtree(x->right,y);
        
        return res;
    }
};