核心考點：二叉樹理解，二叉樹遍歷
輸入兩棵二叉樹A, B，判斷B是不是A的子結構，（ps：我們約定空樹不是任意一個樹的子結構）
決議：
如何理解子結構？
可以理解成子結構是原樹的子樹，或者一部分，也就是說，B要是A的子結構，那么B的根結點+左子樹+右子樹，都在A中存在且構成樹形結構，
如何判斷B是否是A的子結構？
判斷子結構的程序可以分為兩步：
- 先確定起始位置，
- 判斷從確定的位置開始，后續的左右子樹的內容是否一致，
例如，對于以下兩棵樹，我們需要先在A樹當中找到與B樹根結點值相同的結點，然后再判斷從該結點位置開始后續的左右子樹的內容是否一致，
若判斷結果一致，則直接得出B是A的子結構；若判斷結果不一致，則重新在A樹中尋找與B樹根結點值相同的結點，如此進行下去，直到判定B是A的子結構或者A樹被遍歷完畢判定B不是A的子結構，
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
bool IsSame(TreeNode* begin, TreeNode* beginSub)
{
if (beginSub == nullptr) //beginSub為nullptr，說明已經比較完了
return true;
if (begin == nullptr) //beginSub未比較完，但begin已經比較完了
return false;
if (begin->val != beginSub->val) //結點值不相同，回傳false
return false;
//結點值相同，且左子樹和右子樹相同則為相同的樹
return IsSame(begin->left, beginSub->left) && IsSame(begin->right, beginSub->right);
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
if (pRoot1 == nullptr || pRoot2 == nullptr) //pRoot1已經遍歷完畢或pRoot2為空，則回傳false
return false;
bool result = false;
//找到起始位置
if (pRoot1->val == pRoot2->val)
{
//從起始位置開始，判斷兩棵樹是否相同
result = IsSame(pRoot1, pRoot2);
}
//從左子樹尋找匹配的起始位置
if (result != true)
{
result = HasSubtree(pRoot1->left, pRoot2);
}
//從右子樹尋找匹配的起始位置
if (result != true)
{
result = HasSubtree(pRoot1->right, pRoot2);
}
return result;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/352270.html
標籤：其他