ต้นไม้แบนารีที่กลับด้านได้เทียบเท่า (Flip Equivalent Binary Trees) ใน C++

ต้นไม้แบนารีที่กลับด้านได้เทียบเท่า (Flip Equivalent Binary Trees)

การ "กลับด้าน" (flip) หมายถึงเลือกโหนดใดโหนดหนึ่ง แล้วสลับต้นไม้ย่อยซ้ายและขวา ต้นไม้ X และ Y เป็น flip equivalent ถ้าสามารถทำให้ Y ได้จาก X โดยการ flip จำนวนครั้งหนึ่งๆ

ตัวอย่าง: ต้นไม้สองต้นที่ flip โหนดค่า 1, 3, 5 แล้วจะเทียบเท่ากัน ผลลัพธ์ true

ขั้นตอนการแก้ปัญหา (Recursive)

1. กำหนดฟังก์ชัน solve(t1, t2):
2. ถ้า t1 == null && t2 == null คืนค่า true
3. ถ้า t1 == null || t2 == null คืนค่า false
4. ถ้า t1.val != t2.val คืนค่า false
5. ถ้า (ทั้งคู่ไม่มีลูกซ้าย) หรือ (ทั้งคู่มีลูกซ้ายและค่าลูกซ้ายเท่ากัน):
   • คืนค่า solve(t1.left, t2.left) && solve(t1.right, t2.right)
6. มิฉะนั้น (ต้อง flip):
   • คืนค่า solve(t1.left, t2.right) && solve(t1.right, t2.left)

ตัวอย่างโค้ด C++

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        if (!root1 && !root2) return true;
        if (!root1 || !root2) return false;
        if (root1->val != root2->val) return false;
        if ((!root1->left && !root2->left) ||
            (root1->left && root2->left && root1->left->val == root2->left->val)) {
            return flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right);
        } else {
            return flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left);
        }
    }
};

อินพุทและเอาต์พุทตัวอย่าง

Input: [1,2,3,4,5,6,null,null,null,7,8] [1,3,2,null,6,4,5,null,null,null,null,8,7]

Output: 1 (true)