Same Tree trong C++

Kiểm tra hai cây nhị phân có giống hệt nhau không (cấu trúc và giá trị nút).

Ví dụ: [1,2,3] và [1,2,3] → true.

Giải thuật (Đệ quy)

1. Cả hai null → true.
2. Một null, một không → false.
3. Giá trị khác nhau → false.
4. Đệ quy kiểm tra cây con trái và phải.

Ví dụ triển khai C++

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

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

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val 
            && isSameTree(p->left, q->left) 
            && isSameTree(p->right, q->right);
    }
};

// Helper build tree (0 = null)
TreeNode* build(vector<int> v) {
    if (v.empty() || v[0] == 0) return nullptr;
    TreeNode* root = new TreeNode(v[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while (!q.empty() && i < v.size()) {
        TreeNode* cur = q.front(); q.pop();
        if (i < v.size() && v[i] != 0) {
            cur->left = new TreeNode(v[i]);
            q.push(cur->left);
        }
        i++;
        if (i < v.size() && v[i] != 0) {
            cur->right = new TreeNode(v[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main() {
    Solution ob;
    vector<int> a = {1,2,3}, b = {1,2,3};
    cout << boolalpha << ob.isSameTree(build(a), build(b)); // true
    return 0;
}

Đầu vào / Đầu ra

Input: {1,2,3}, {1,2,3}
Output: true (1)