題目：

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

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

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

示例：

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

解題思路：

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

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

源代碼如下：

class Solution {
public:bool dfs(TreeNode* t1,TreeNode* t2){if(t1==NULL&&t2==NULL) return true;//同時(shí)為空，返回trueif(t1==NULL||t2==NULL) return false;//只有一個(gè)為空，則一定不相等，返回false//節(jié)點(diǎn)值相等 ，繼續(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é)點(diǎn)的值與T2的節(jié)點(diǎn)值相同，則開始遞歸的找其他節(jié)點(diǎn)是否相等if(t1->val==t2->val){if(dfs(t1,t2)){return true;}}//在T1中找到與T2根節(jié)點(diǎn)值相同的節(jié)點(diǎn)return checkSubTree(t1->left,t2)||checkSubTree(t1->right,t2);}
};