本文共 2067 字，大约阅读时间需要 6 分钟。

题目：树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:

     3

给定的树 B：

   4 

示例 1：

输入：A = [1,2,3], B = [3,1]输出：false

示例 2：

输入：A = [3,4,5,1,2], B = [4,1]输出：true

限制：

0 <= 节点个数 <= 10000

解题：

• 首先要遍历A找出与B根节点一样值的节点R
• 然后判断树A中以R为根节点的子树是否包含和B一样的结构
• 注意：空树不是任意一个树的子结构

/** * 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) {        bool res = false;        //当TreeA和TreeB都不为零的时候，才进行比较。否则直接返回false        if (A!=NULL && B!=NULL)        {            //如果找到了对应TreeB的根节点的点            if (A->val == B->val)                //以这个根节点为为起点判断是否包含TreeB                res = helper(A, B);            //如果找不到，那么就再去TreeA的左子树当作起点，去判断是否包含TreeB            if (!res)                res = isSubStructure(A->left, B);            //如果还找不到，那么就再去TreeA的右子树当作起点，去判断是否包含TreeB            if (!res)                res = isSubStructure(A->right, B);        }        // 返回结果        return res;    }    bool helper(TreeNode* A, TreeNode* B)    {        //如果TreeB已经遍历完了都能对应的上，返回true        if (B==NULL)            return true;        //如果TreeB还没有遍历完，TreeA却遍历完了。返回false        if (A==NULL)            return false;        //如果其中有一个点没有对应上，返回false        if (A->val != B->val)            return false;        //如果根节点对应的上，那么就分别去子节点里面匹配        return helper(A->left, B->left) && helper(A->right, B->right);    }};

简化代码：

class Solution {public:    bool isSubStructure(TreeNode* A, TreeNode* B) {        if (A == NULL || B == NULL) {            return false;        }        return helper(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);    }    bool helper(TreeNode* A, TreeNode* B) {        if (A == NULL || B == NULL) {            return B == NULL ? true : false;        }        if (A->val != B->val) {            return false;        }        return helper(A->left, B->left) && helper(A->right, B->right);    }};

转载地址：http://kbgen.baihongyu.com/