題目：

檢查子樹。你有兩棵非常大的二叉樹：T1，有幾萬個節(jié)點；T2，有幾萬個節(jié)點。設(shè)計一個算法，判斷 T2 是否為 T1 的子樹。

如果 T1 有這么一個節(jié)點 n，其子樹與 T2 一模一樣，則 T2 為 T1 的子樹，也就是說，從節(jié)點 n 處把樹砍斷，得到的樹與 T2 完全相同。

注意：這道題與找不同的地方在于“從節(jié)點 n 處把樹砍斷，得到的樹與 T2 完全相同”，所以必須要找到葉子節(jié)點，這期間的所有節(jié)點都相同，才是子樹，否則不是子樹

示例：

?輸入：t1 = [1, 2, 3], t2 = [2]
?輸出：true
? 輸入：t1 = [1, 2, 3，4，5], t2 = [2]
?輸出：false

解題思路：

1.先遞歸地找到T1樹中與T2的根節(jié)點相同的節(jié)點

2.再遞歸地找剩下的節(jié)點是否每一個都相等

源代碼如下：

class Solution {
public:bool dfs(TreeNode* t1,TreeNode* t2){if(t1==NULL&&t2==NULL) return true;//同時為空，返回trueif(t1==NULL||t2==NULL) return false;//只有一個為空，則一定不相等，返回false//節(jié)點值相等 ，繼續(xù)遞歸if(t1->val==t2->val){return dfs(t1->left,t2->left)&&dfs(t1->right,t2->right);}//一旦出現(xiàn)不相等的情況，直接返回falseelse return false;}bool checkSubTree(TreeNode* t1, TreeNode* t2) {if(t1==NULL&&t2==NULL) return true;//兩顆都是空樹，則返回trueif(t1==NULL||t2==NULL) return false;//只有一顆樹為空，那么一定不存在子樹，返回false//如果T1節(jié)點的值與T2的節(jié)點值相同，則開始遞歸的找其他節(jié)點是否相等if(t1->val==t2->val){if(dfs(t1,t2)){return true;}}//在T1中找到與T2根節(jié)點值相同的節(jié)點return checkSubTree(t1->left,t2)||checkSubTree(t1->right,t2);}
};