1. 題目

檢查子樹。你有兩棵非常大的二叉樹：T1，有幾萬個節(jié)點；T2，有幾萬個節(jié)點。

設(shè)計一個算法，判斷 T2 是否為 T1 的子樹。

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

示例1:輸入：t1 = [1, 2, 3], t2 = [2]輸出：true示例2:輸入：t1 = [1, null, 2, 4], t2 = [3, 2]輸出：false 提示： 樹的節(jié)點數(shù)目范圍為[0, 20000]。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/check-subtree-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 找到跟 t2 根節(jié)點值一樣的節(jié)點，開啟 check

class Solution {bool found = false; public:bool checkSubTree(TreeNode* t1, TreeNode* t2) {if(!t2)return true;else if(!t1)return false;if(t1->val == t2->val){found = check(t1, t2);}checkSubTree(t1->left, t2);checkSubTree(t1->right, t2);return found;}bool check(TreeNode* t1, TreeNode* t2) {if(found)return true;if(!t1 && t2)return false;else if(!t2)return true;else{if(t1->val != t2->val)return false;return check(t1->left, t2->left) && check(t1->right, t2->right);}} };

總結(jié)

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 04.10. 检查子树（双重递归）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。