ทรีย่อยกลับด้านใน C ++

สมมติว่าเรามีต้นไม้ไบนารีสองต้นที่เรียกว่าต้นทางและเป้าหมาย เราต้องตรวจสอบว่ามีการผกผันของต้นทาง T หรือไม่ว่าเป็นแผนผังย่อยของเป้าหมาย ดังนั้นจึงหมายความว่ามีโหนดในเป้าหมายที่เหมือนกันในค่าและโครงสร้างเหมือนกับ T รวมถึงลูกหลานทั้งหมดด้วย

ดังที่เราทราบกันดีว่ามีการกล่าวกันว่าต้นไม้เป็นการผกผันของต้นไม้อื่นหากเป็นเช่นนั้น -

• ว่างทั้งสองต้น

• ลูกซ้ายและขวาของมันจะสลับกันได้ และทรีย่อยซ้ายและขวาของมันคือผกผัน

ดังนั้นหากอินพุตเป็นเหมือนแหล่งสัญญาณ

เป้าหมาย

แล้วผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน check() ซึ่งจะใช้ node1, node2,

• ถ้าทั้ง node1 และ node2 เป็นโมฆะ −

  • คืนความจริง

• ถ้า node1 หรือ node2 อันใดอันหนึ่งเป็นโมฆะ −

  • คืนค่าเท็จ

• ถ้า val ของ node1 ไม่เท่ากับ val ของ node2 แล้ว −

  • คืนค่าเท็จ

• op1 :=ตรวจสอบ (ด้านซ้ายของ node1 ด้านซ้ายของ node2) และตรวจสอบ (ด้านขวาของ node1 ด้านขวาของ node2)

• op2 :=ตรวจสอบ (ด้านขวาของโหนด 1 ด้านซ้ายของโหนด2) และตรวจสอบ (ด้านซ้ายของโหนด 1 ด้านขวาของโหนด2)

• คืนค่า จริง เมื่อ op1 และ op2 อย่างน้อยหนึ่งรายการเป็นจริง

• กำหนดฟังก์ชัน Solve() ซึ่งจะใช้ซอร์ส เป้าหมาย

• หากต้นทางและเป้าหมายว่างเปล่า −

  • คืนความจริง

• ถ้าต้นทางหรือเป้าหมายอันใดอันหนึ่งเป็นโมฆะ -

  • คืนค่าเท็จ

• op1 :=ตรวจสอบ (เป้าหมาย, แหล่งที่มา)

• ถ้า op1 เป็นจริง −

  • คืนความจริง

• คืนค่า จริง เมื่อการแก้ (ต้นทาง, ด้านซ้ายของเป้าหมาย) อย่างน้อยหนึ่งรายการ หรือ การแก้ (ต้นทาง, ทางขวาของเป้าหมาย) เป็นจริง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

#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 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;
      bool op1 = check(target, source);
      if(op1)
         return true;
      return solve(source, target->left) || solve(source, target->right);
   }
};
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