1括荡、題目描述
輸入兩棵二叉樹A高镐，B，判斷B是不是A的子結(jié)構(gòu)畸冲。
我們規(guī)定空樹不是任何樹的子結(jié)構(gòu)嫉髓。
樣例
樹A
8
/ \
8 7
/ \
9 2
?? / \
? 4 7
樹B：
8
/ \
9 2
返回 true ,因?yàn)锽是A的子結(jié)構(gòu)。
2邑闲、問(wèn)題描述：
3算行、問(wèn)題關(guān)鍵：
- 兩層遞歸，遞歸每個(gè)結(jié)點(diǎn)為起點(diǎn)的樹苫耸。遞歸每個(gè)樹的對(duì)應(yīng)的點(diǎn)州邢。
4、C++代碼：
/**
* 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 hasSubtree(TreeNode* p1, TreeNode* p2) {
if (!p1 || !p2) return false;
if (help(p1, p2)) return true;
return hasSubtree(p1->left, p2) || hasSubtree(p1->right, p2);//這個(gè)地方的遞歸是對(duì)所有的子樹遞歸褪子。
}
bool help(TreeNode *p1, TreeNode *p2) {
if (!p2) return true;
if (!p1 || p1->val != p2->val) return false;
return help(p1->left, p2->left) && help(p1->right, p2->right);//這個(gè)地方的遞歸是對(duì)當(dāng)前樹的遞歸量淌。
}
};
