一、题目
限制：0 <= 节点个数 <= 10000
二、思路
题目判断的是B是否为A树的【子结构】，而不判断是【子树】。
直观的思路：
从A的每个节点开始逐个（递归）遍历，（假设当前的节点为K）；
然后判断B树，是否为当前以K节点为头结点的子结构。
上面第二步，对应下面代码的issame部分：
如果B树为空（先遍历完了），则是子结构；
如果B树不空，A树为空（A树先遍历完了），则不是子结构；
AB树当前节点都不空了，但是val不相同，也不是子结构了；
AB树当前节点都不空，并且val相同（暂时满足），继续分别递归A和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) { //约定空树不是任意一个树的子结构 if(!A || !B) return false; //第二部分 if(issame(A, B)) return true; return isSubStructure(A->left, B) || isSubStructure(A->right, B); } bool issame(TreeNode* a, TreeNode* b){ if(!b) return true; if(!a) return false; if(a->val != b->val) return false; //两棵子树的当前节点相同，递归遍历 return issame(a->left, b->left) && issame(a->right, b->right); } };
