Symmetric Tree (ต้นไม้สมมาตร) ใน C++

โจทย์

กำหนด Binary Tree ตรวจสอบว่าเป็น Symmetric Tree หรือไม่ (Mirror image ของตัวเอง)

ตัวอย่าง

Input 1: Tree ที่สมมาตร → Output: True

Input 2: Tree ไม่สมมาตร → Output: False

แนวคิดการแก้

Tree สมมาตร ⟺ Left Subtree และ Right Subtree เป็น Mirror กัน

Recursive check: isMirror(left, right)

• ทั้งคู่ NULL → True
• หนึ่ง NULL อีกไม่ → False
• ค่าเท่ากัน และ left->left mirror right->right และ left->right mirror right->left

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isMirror(TreeNode* left, TreeNode* right) {
    if (!left && !right) return true;
    if (!left || !right) return false;
    return (left->val == right->val) 
        && isMirror(left->left, right->right)
        && isMirror(left->right, right->left);
}

bool isSymmetric(TreeNode* root) {
    if (!root) return true;
    return isMirror(root->left, root->right);
}

// Helper: สร้างโหนดทดสอบ
TreeNode* createNode(int val) {
    return new TreeNode(val);
}

int main() {
    // Test Case 1: Symmetric
    //       4
    //      / \
    //     2   2
    //    / \ / \
    //   5  7 7  5
    TreeNode* root1 = createNode(4);
    root1->left = createNode(2);
    root1->right = createNode(2);
    root1->left->left = createNode(5);
    root1->left->right = createNode(7);
    root1->right->left = createNode(7);
    root1->right->right = createNode(5);
    
    cout << "Test 1: " << (isSymmetric(root1) ? "True" : "False") << endl; // True
    
    // Test Case 2: Not Symmetric
    //       1
    //      / \
    //     2   2
    //      \   \
    //       3   3
    TreeNode* root2 = createNode(1);
    root2->left = createNode(2);
    root2->right = createNode(2);
    root2->left->right = createNode(3);
    root2->right->right = createNode(3);
    
    cout << "Test 2: " << (isSymmetric(root2) ? "True" : "False") << endl; // False
    
    return 0;
}

Complexity

• Time: O(n) - เยี่ยมทุกโหนด 1 ครั้ง
• Space: O(h) - Recursion stack = ความสูงต้นไม้ (Worst O(n) สำหรับ Skewed tree)

Iterative Approach (BFS)

bool isSymmetricIterative(TreeNode* root) {
    if (!root) return true;
    queue<TreeNode*> q;
    q.push(root->left);
    q.push(root->right);
    
    while (!q.empty()) {
        TreeNode* n1 = q.front(); q.pop();
        TreeNode* n2 = q.front(); q.pop();
        
        if (!n1 && !n2) continue;
        if (!n1 || !n2) return false;
        if (n1->val != n2->val) return false;
        
        q.push(n1->left);  q.push(n2->right);
        q.push(n1->right); q.push(n2->left);
    }
    return true;
}

ผลลัพธ์

Test 1: True
Test 2: False

สรุป

Symmetric Tree ตรวจสอบได้ด้วย Recursive (กระชับ) หรือ Iterative (Queue) ทั้งคู่ Time O(n) เลือกตามสไตล์และข้อจำกัด Stack