從LeetCode 100和101看二叉樹的比較與對稱性判斷

今天要講的是leetcode100.相同的樹，并且本文章還會講到延伸題型leetcode101.對稱二叉樹。本文章編寫用的是C語言，大家主要是學習思路，學習過后可以自己點擊鏈接測試，并且做一些對應的生題，現在就讓我們開始吧！

一、題目簡介

LeetCode 100：相同的樹

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

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

示例 1：

輸入：p = [1,2,3], q = [1,2,3]
輸出：true

示例 2：

輸入：p = [1,2], q = [1,null,2]
輸出：false

示例 3：

輸入：p = [1,2,1], q = [1,1,2]
輸出：false

提示：

• 兩棵樹上的節點數目都在范圍?[0, 100]?內
• -104 <= Node.val <= 104

LeetCode 101:? ?對稱二叉樹

給你一個二叉樹的根節點?root?， 檢查它是否軸對稱。

示例 1：

輸入：root = [1,2,2,3,4,4,3]
輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3]
輸出：false

提示：

• 樹中節點數目在范圍?[1, 1000]?內
• -100 <= Node.val <= 100

進階：你可以運用遞歸和迭代兩種方法解決這個問題嗎？

二、思路詳解

題目一：LeetCode 100（相同的樹）

1. 問題分析

這道題里有一個小坑，如果我們單純只通過遍歷來比對是否相等的話，是無法保證二叉樹的結構相同的，僅僅只能保證該顆二叉樹所包含的節點數值是一致的，但是我們將一顆樹分為多個部分來比對就會方便很多，將兩棵樹對應的左子樹與左子樹比對，右子樹和右子樹比對。

2. 解題思路

我們可以使用遞歸的方法來解決這個問題。遞歸的基本思路如下：

• 如果兩個節點都為空，返回 true。

• 如果一個節點為空而另一個不為空，返回 false。

• 如果兩個節點的值不同，返回 false。

• 遞歸地比較左子樹和右子樹。

3. C語言實現

#include <stdbool.h>// 定義二叉樹節點結構
typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 遞歸函數，比較兩個節點
bool isSameTree(TreeNode* p, TreeNode* q) {// 如果兩個節點都為空，返回trueif (p == NULL && q == NULL) {return true;}// 如果一個為空，另一個不為空，返回falseif (p == NULL || q == NULL) {return false;}// 如果兩個節點的值不同，返回falseif (p->val != q->val) {return false;}// 遞歸比較左子樹和右子樹return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

題目二：LeetCode 101（對稱二叉樹）

1. 問題分析

這道題與上一道題（LeetCode 100：相同的樹）是很相似，但有兩個關鍵的不同點：

1. 參數不同：這道題只傳入一個根節點，即只有一棵樹。

2. 判斷條件不同：這道題要求判斷的是對稱二叉樹，即鏡像相同。具體來說，左子樹的左節點應該與右子樹的右節點相同，左子樹的右節點應該與右子樹的左節點相同。

2. 解題思路

為了解決上述兩個不同點，我們可以通過構造一個新的函數來實現將一棵樹“一分為二”，再對兩側的左右子樹進行比較。遞歸的基本思路如下：

1. 遞歸終止條件：

   • 如果兩個節點都為空，返回 true，表示這部分是鏡像對稱的。

   • 如果一個節點為空而另一個不為空，返回 false，表示這部分不對稱。

2. 遞歸邏輯：

   • 如果兩個節點的值相同，繼續遞歸比較左子樹的左節點與右子樹的右節點，以及左子樹的右節點與右子樹的左節點。

   • 如果兩個節點的值不同，直接返回 false。

3. C語言實現

#include <stdbool.h>// 定義二叉樹節點結構
typedef struct TreeNode {int val;                     // 節點的值struct TreeNode *left;       // 指向左子節點的指針struct TreeNode *right;      // 指向右子節點的指針
} TreeNode;// 輔助函數：檢查兩個節點是否鏡像對稱
bool check(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 check(p->left, q->right) && check(p->right, q->left);}// 如果兩個節點的值不同，直接返回falsereturn false;
}// 主函數：判斷整棵樹是否對稱
bool isSymmetric(struct TreeNode* root) {// 從根節點開始，調用輔助函數檢查整棵樹是否對稱return check(root, root);
}

#include <stdbool.h>// 定義二叉樹節點結構
typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;// 使用迭代方法（層次遍歷）判斷二叉樹是否對稱
bool isSymmetric(struct TreeNode* root) {// 如果根節點為空，直接返回 true（空樹是對稱的）if (root == NULL) return true;// 使用數組模擬隊列struct TreeNode* queue[1000];// head 和 tail 分別指向隊列的頭部和尾部int head = 0, tail = 0;// 將根節點的左右子樹加入隊列queue[tail++] = root->left;queue[tail++] = root->right;// 循環結束條件：隊列為空（head == tail）while (head != tail) {// 從隊列中取出兩個節點進行比較struct TreeNode* leftNode = queue[head++];struct TreeNode* rightNode = queue[head++];// 如果一個節點為空而另一個不為空，說明不對稱，返回 falseif (leftNode == NULL && rightNode != NULL) return false;if (leftNode != NULL && rightNode == NULL) return false;// 如果兩個節點都為空，跳過本輪循環，繼續下一對節點的比較if (leftNode == NULL && rightNode == NULL) continue;// 如果兩個節點的值不相等，說明不對稱，返回 falseif (leftNode->val != rightNode->val) return false;// 將左節點的左子節點和右節點的右子節點加入隊列queue[tail++] = leftNode->left;queue[tail++] = rightNode->right;// 將左節點的右子節點和右節點的左子節點加入隊列queue[tail++] = leftNode->right;queue[tail++] = rightNode->left;}// 如果隊列為空且沒有發現不對稱的情況，返回 truereturn true;
}