1. 題目

給定兩個非空二叉樹 s 和 t，檢驗 s 中是否包含和 t 具有相同結(jié)構(gòu)和節(jié)點值的子樹。s 的一個子樹包括 s 的一個節(jié)點和這個節(jié)點的所有子孫。s 也可以看做它自身的一棵子樹。

示例 1: 給定的樹 s:3/ \4 5/ \1 2 給定的樹 t：4 / \1 2 返回 true，因為 t 與 s 的一個子樹擁有相同的結(jié)構(gòu)和節(jié)點值。示例 2: 給定的樹 s：3/ \4 5/ \1 2/0 給定的樹 t：4/ \1 2 返回 false。

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

2. 二叉樹迭代器

• 對樹s中的每個節(jié)點Si，Si與t進行遞歸比較
• Si采用二叉樹迭代器產(chǎn)生
• 該解法相當于暴力查找

class Solution {TreeNode *cur, *temp;stack<TreeNode*> stk; public:bool isSubtree(TreeNode* s, TreeNode* t) {cur = s;bool ans = false;TreeNode *Si = next();//Si為二叉樹的每個節(jié)點while(!ans && Si != NULL)//沒有答案，Si還沒遍歷完{ans = isSub(Si,t);//對每個節(jié)點開始，跟t進行比較Si = next();}return ans;}bool isSub(TreeNode *s, TreeNode *t)//比較Si與t的結(jié)構(gòu)相同嗎？{if(!s && !t)return true;else if((!s && t) || (s && !t))return false;if(s->val == t->val)//相等，還要繼續(xù)比較子樹return isSub(s->left,t->left)&&isSub(s->right,t->right);return false;}TreeNode* next()//二叉樹迭代器{while(cur || !stk.empty()){while(cur){stk.push(cur);cur = cur->left;}temp = stk.top();cur = stk.top()->right;stk.pop();return temp;}return NULL;} };

• 別人的解法總是很優(yōu)雅

class Solution { public:bool isSubtree(TreeNode* s, TreeNode* t) {if (!s) return false;return isSubtree(s->left, t) || SameTree(s, t) || isSubtree(s->right, t);}bool SameTree(TreeNode* s, TreeNode* t) {if (!s && !t) return true;if (!s || !t) return false;return s->val == t->val && SameTree(s->left, t->left) && SameTree(s->right, t->right);} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 572. 另一个树的子树（二叉树迭代器）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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