原問題網址:101. Symmetric Tree
問題描述
給定一棵 Binary Tree 的 root
,檢查其結構是否圍繞中心對稱(左右子樹就像鏡子反射一樣)。
解題思路
- 使用遞迴解決。
- 如果它沒有左子樹也沒有右子樹,必為
true
。 - 如果有左子樹但沒有右子樹,或是有右子樹但沒有左子樹,必為
false
,因為左右一定不對稱。 - 定義另一個 function
is_mirror
檢查兩棵 Binary Tree 是否互為鏡像。
- 兩棵 Binary Tree 的 root 的 value 一定要相等,否則必為
false
。 - 比較 tricky 的部分:如果第一棵 tree 的左子點為
NULL
,第二棵 tree 的右子點也一定要為NULL
,否則為false
,反之亦然。
以下為用 C 語言實作的程式碼:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool is_mirror(struct TreeNode* root1, struct TreeNode* root2) {
if (root1 == NULL || root2 == NULL) {
return false;
}
if (root1->val != root2->val) {
return false;
}
if (root1->left == NULL && root2->right != NULL) {
return false;
}
if (root1->right == NULL && root2->left != NULL) {
return false;
}
if (root1->left != NULL) {
if (!is_mirror(root1->left, root2->right)) {
return false;
}
}
if (root1->right != NULL) {
if (!is_mirror(root1->right, root2->left)) {
return false;
}
}
return true;
}
bool isSymmetric(struct TreeNode* root){
if (root->left == NULL && root->right == NULL) {
return true;
}
if (root->left == NULL || root->right == NULL) {
return false;
}
return is_mirror(root->left, root->right);
}