Description

101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true
Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

Answer & Explaining

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h> // 包含 malloc() 的標頭檔

// 判斷兩個subtree是否對稱
 
bool isMirror(struct TreeNode* left, struct TreeNode* right) {
    // 如果兩個subtree都為空，則對稱
    if (left == NULL && right == NULL) {
        return true;
    }

    // 如果只有一個subtree為空，則不對稱
    if (left == NULL || right == NULL) {
        return false;
    }

    // 如果當前node值相同，則遞迴比較
    return (left->val == right->val) &&
           isMirror(left->left, right->right) &&
           isMirror(left->right, right->left);
}

// 判斷binary tree是否是對稱的

bool isSymmetric(struct TreeNode* root) {
    // 如果樹是空的，則對稱
    if (root == NULL) {
        return true;
    }

    // 檢查left subtree, right subtree是否對稱
    return isMirror(root->left, root->right);
}

Testing

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h> // 包含 malloc() 的標頭檔


//定義binary tree node
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

// 判斷兩個subtree是否對稱
 
bool isMirror(struct TreeNode* left, struct TreeNode* right) {
    // 如果兩個subtree都為空，則對稱
    if (left == NULL && right == NULL) {
        return true;
    }

    // 如果只有一個subtree為空，則不對稱
    if (left == NULL || right == NULL) {
        return false;
    }

    // 如果當前node值相同，則遞迴比較
    return (left->val == right->val) &&
           isMirror(left->left, right->right) &&
           isMirror(left->right, right->left);
}

// 判斷binary tree是否是對稱的

bool isSymmetric(struct TreeNode* root) {
    // 如果樹是空的，則對稱
    if (root == NULL) {
        return true;
    }

    // 檢查left subtree, right subtree是否對稱
    return isMirror(root->left, root->right);
}

// 測試函數
struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 測試範例
void testIsSymmetric() {
    // 測試範例1: [1,2,2,3,4,4,3]
    struct TreeNode* root1 = createNode(1);
    root1->left = createNode(2);
    root1->right = createNode(2);
    root1->left->left = createNode(3);
    root1->left->right = createNode(4);
    root1->right->left = createNode(4);
    root1->right->right = createNode(3);
    printf("Test case 1 (should be true): %s\n", isSymmetric(root1) ? "true" : "false");

    // 測試範例2: [1,2,2,null,3,null,3]
    struct TreeNode* root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(2);
    root2->left->right = createNode(3);
    root2->right->right = createNode(3);
    printf("Test case 2 (should be false): %s\n", isSymmetric(root2) ? "true" : "false");
}

// 主要測試函數
int main() {
    testIsSymmetric();
    return 0;
}