題目一 相同的樹

給你兩棵二叉樹的根節點 p 和 q ，編寫一個函數來檢驗這兩棵樹是否相同。

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。

首先我們要來判斷下它們的根是否相等

根相等的話是否它們的左子樹相等

是否它們的右子樹相等

一直到子樹為空為止

大家仔細思考下這個思路對不對

接下來我們開始敲代碼

首先我們想極端一點的情況

如果這個倆空指針

說明這里肯定不用判斷了 返回ture就行

如果說有一個空指針 一個不為空指針的話 那么肯定是不相同的返回假就可以

接下來如果值相等 我們能判斷它們相同嘛 顯然不可以

所以說我們這里直接上兩個不同 返回假

之后我們再判斷它的左子樹右子樹

整體代碼如下

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p==NULL&&q==NULL){return true;}//一方為空if(p==NULL||q==NULL){return false;}//都不為空if(p->val!=q->val){return false;}return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

測試一下?

可以運行

題目二 對稱二叉樹

這里和前面相同的數的思路差不多

都是判斷極值條件

我們可以借用一下前面的代碼稍微修改一下，將左右子樹比較

之后遞歸展開 這里直接上代碼 代碼中會寫明解題思路

 bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if(p==NULL&&q==NULL){return true;}//一方為空if(p==NULL||q==NULL){return false;}//都不為空if(p->val!=q->val){return false;}return isSameTree(p->left,q->right)&&isSameTree(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root) {if(root==NULL){return true;}return isSameTree(root->left,root->right);
}

這里我們要注意的是 要轉換成兩個子樹問題才可以做

而子樹問題需要再創建一個遞歸函數 可能是這一題的難點之一

還有一個難點就是要觀察結構、

題目三 另一個樹的子樹

給你兩棵二叉樹 root 和 subRoot 。檢驗 root 中是否包含和 subRoot 具有相同結構和節點值的子樹。如果存在，返回 true ；否則，返回 false 。

二叉樹 tree 的一棵子樹包括 tree 的某個節點和這個節點的所有后代節點。tree 也可以看做它自身的一棵子樹。

來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/subtree-of-another-tree

我們這里只需要遍歷一遍root 并且將root中的每一個節點和subroot比較一次就可以

遍歷會吧

比較會吧

連起來

過啦！

代碼表示如下

bool isSameTree(struct TreeNode* p, struct TreeNode* q) {if (p == NULL && q == NULL){return true;}//一方為空if (p == NULL || q == NULL){return false;}//都不為空if (p->val != q->val){return false;}return isSameTree(p->left, q->left)&& isSameTree(p->right, q->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){if(root==NULL){return false;}if(isSameTree(root,subRoot)){return true;}return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);
}

?以上便是本文所有內容，如有錯誤請各位大佬不吝賜教，感謝留言?