Xác Thực Các Nút Cây Nhị Phân Trong C++

Giả sử chúng ta có n nút cây nhị phân đánh số 0 đến n-1, nút i có hai con leftChild[i] và rightChild[i]. Xác định xem tất cả các nút đã cho có hình thành đúng một cây nhị phân hợp lệ hay không. Nếu nút i không có con trái thì leftChild[i] = -1, tương tự cho con phải. Các nút không có giá trị, chỉ dùng số thứ tự.

Ví dụ như hình → true.

Để giải quyết, chúng ta làm theo các bước:

• Định nghĩa dfs(node, leftChild, rightChild, visited): nếu node đã visited trả về false; thêm node vào visited; ret = true; nếu leftChild[node] != -1: ret &= dfs(leftChild[node], ...); nếu rightChild[node] != -1: ret &= dfs(rightChild[node], ...); trả về ret.

• Từ main: ret = dfs(0, leftChild, rightChild, visited); kiểm tra allVisited: với i từ 0 đến n-1 nếu i không trong visited trả về false; trả về ret.

Ví dụ (C++)

Hãy xem triển khai sau để hiểu rõ hơn:

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

class Solution {
public:
    bool dfs(int node, vector <int>& leftChild, vector <int>& rightChild, set <int>& visited){
        if(visited.count(node)) return false;
        visited.insert(node);
        bool ret = true;
        if(leftChild[node] != -1){
            ret &= dfs(leftChild[node], leftChild, rightChild, visited);
        }
        if(rightChild[node] != -1){
            ret &= dfs(rightChild[node], leftChild, rightChild, visited);
        }
        return ret;
    }
    bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
        set <int> visited;
        bool ret = dfs(0, leftChild, rightChild, visited);
        bool allVisited = true;
        for(int i = 0; i < n; i++){
            if(!visited.count(i)) return false;
        }
        return ret;
    }
};

int main(){
    vector<int> v1 = {1,-1,3,-1}, v2 = {2,-1,-1,-1};
    Solution ob;
    cout << (ob.validateBinaryTreeNodes(4, v1, v2));
}

Đầu vào

4 [1,-1,3,-1] [2,-1,-1,-1]

Đầu ra

1