Inverted Subtree in C++

สมมติว่าเรามีต้นไม้ไบนารีสองต้น source และ target เราต้องตรวจสอบว่ามีการกลับด้าน (inversion) T ของ source ใดๆ ที่เป็นซับทรี (subtree) ของ target หรือไม่ หมายถึงมีโหนดใน target ที่เหมือน T ทุกประการทั้งค่าและโครงสร้างรวมถึงลูกหลานทั้งหมด

ต้นไม้สองต้นถูกกลับด้านกัน (inversion) ถ้า:

• ทั้งสองว่างเปล่า, หรือ
• ลูกซ้ายและขวาสลับได้ และซับทรีซ้าย-ขวาเป็นการกลับด้านกัน

เช่น ต้นไม้ source และ target ตามภาพ ผลลัพธ์จะเป็น True

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

• ฟังก์ชัน check(node1, node2): ตรวจสอบว่า node1 และ node2 เป็นการกลับด้านกันหรือไม่
  • ทั้งคู่ null: true
  • ใดๆ หนึ่ง null: false
  • ค่าไม่เท่ากัน: false
  • op1 = check(left1, left2) && check(right1, right2) (ไม่สลับ)
  • op2 = check(right1, left2) && check(left1, right2) (สลับ)
  • return op1 || op2
• ฟังก์ชัน solve(source, target): หาใน target ว่ามีซับทรีที่เป็นการกลับด้านของ source
  • ถ้า check(target, source) เป็น true: return true
  • return solve(source, target->left) || solve(source, target->right)

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

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

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

class Solution {
public:
    bool check(TreeNode* node1, TreeNode* node2) {
        if (!node1 && !node2) return true;
        if (!node1 || !node2) return false;
        if (node1->val != node2->val) return false;
        bool op1 = check(node1->left, node2->left) && check(node1->right, node2->right);
        bool op2 = check(node1->right, node2->left) && check(node1->left, node2->right);
        return op1 || op2;
    }
    bool solve(TreeNode* source, TreeNode* target) {
        if (!target && !source) return true;
        if (!target || !source) return false;
        if (check(target, source)) return true;
        return solve(source, target->left) || solve(source, target->right);
    }
};

int main() {
    Solution ob;
    TreeNode *target = new TreeNode(6);
    target->left = new TreeNode(3);
    target->right = new TreeNode(1);
    target->right->left = new TreeNode(3);
    target->right->right = new TreeNode(2);
    target->right->right->left = new TreeNode(4);
    TreeNode *source = new TreeNode(1);
    source->left = new TreeNode(2);
    source->right = new TreeNode(3);
    source->left->right = new TreeNode(4);
    cout << (ob.solve(source, target));
}

อินพุต

TreeNode *target = new TreeNode(6); target->left = new TreeNode(3); target->right = new TreeNode(1); target->right->left = new TreeNode(3); target->right->right = new TreeNode(2); target->right->right->left = new TreeNode(4); TreeNode *source = new TreeNode(1); source->left = new TreeNode(2); source->right = new TreeNode(3); source->left->right = new TreeNode(4);

เอาต์พุต

1