Same Tree ใน C++

แนวคิด

สมมติว่ามี binary trees สองต้น ให้กำหนดฟังก์ชันตรวจสอบว่าทั้งสองเหมือนกันหรือไม่ Binary trees ถือว่าเหมือนกันเมื่อโครงสร้างเหมือนกันและโหนดมีค่าเท่ากัน

เช่น ถ้าอินพุตคือ [1,2,3],[1,2,3] ผลลัพธ์คือ True

วิธีแก้:

• กำหนดฟังก์ชัน isSameTree รับโหนด p และ q
• ถ้า p เป็น NULL และ q เป็น NULL: คืนค่า true
• ถ้า p เป็น NULL หรือ q เป็น NULL: คืนค่า false
• ถ้า val ของ p เท่ากับ val ของ q และ isSameTree(left of p, left of q) เป็น true และ isSameTree(right of p, right of q) เป็น true: คืนค่า true
• คืนค่า false

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0);
            return;
        } else { q.push(temp->left); }
        if(!temp->right){
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0);
            return;
        } else { q.push(temp->right); }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); }
    return root;
}
class Solution {
public:
    bool isSameTree(TreeNode *p, TreeNode* q){
        if (p == NULL && q == NULL) return true;
        if (p == NULL || q == NULL) return false;
        if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right)) return true;
        return false;
    }
};
main() {
    Solution ob;
    vector<int> v = {1,2,3}, v1 = {1,2,3};
    TreeNode *root1 = make_tree(v);
    TreeNode *root2 = make_tree(v1);
    cout << (ob.isSameTree(root1, root2));
}

อินพุต

{1,2,3}, {1,2,3}

เอาต์พุต

1