涉及到遞歸，最好多畫圖理解，希望對你們有幫助

---

100.相同的樹

題目

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

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

題目鏈接

力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺

文字 和 畫圖 分析

1. 思考遞歸進行的條件和結束的條件是什么
2. 列舉遞歸可能會出現的情況

針對上面兩個問題進行解答：

要想找兩個樹的結構相同有點麻煩，換個思路，我們找它們不同

所以我們需要先對比兩者的根節點，再去對比左子樹和右子樹

[很明顯，我們采取的是 前序 遍歷整個節點]

• 在遞歸的時候，每一次根節點都發生變化，只要根節點對應的數值不同， 就返回 false 結束遞歸 (其中一種結束條件)

• 根節點相同，我們無法判斷是否兩個樹結構相同，只能繼續遞歸（這是遞歸條件）

• 遞歸期間，我們還可能碰到以下情況：

如上圖：我們遇到空樹了

這里還需要分兩種情況討論：

如果兩個樹在這個節點都是空，則返回 true (這是其中一種結束條件)

[注意：我們是先對比根，再對比左子樹，最后對比右子樹，所以只有左子樹和右子樹都為 true 才是一樣的樹]

如果兩個樹只有一個為空，則返回 false (這是其中一種結束條件)

? 3. 判斷的順序問題

由于可能會遇到空樹，先比較根的大小明顯是不行的，所以應該把比較是否是空樹的條件放前面

---

代碼

bool isSameTree(struct TreeNode* p, struct TreeNode* q) 
{if ((p == NULL && q != NULL) || (p != NULL && q == NULL)){return false;}if (p == NULL && q == NULL){return true;}if (p->val != q->val){return false;}return isSameTree(p->left, q->left)  && isSameTree(p->right, q->right);
}