นับ Subtree ที่มีค่าเหมือนกันทั้งหมดใน C++

สมมติว่าเรามีต้นไม้แบบทวิภาค (binary tree) เราต้องนับจำนวน uni-value subtrees ซึ่งหมายถึง subtree ที่ทุกโหนดมีค่าเท่ากันทั้งหมด

ตัวอย่างเช่น ถ้าข้อมูลนำเข้าเป็น root = [5,1,5,5,5,null,5]

ผลลัพธ์จะเป็น 4

วิธีแก้ปัญหา

สร้างฟังก์ชัน solve() ที่รับพารามิเตอร์เป็นโหนด
ถ้าโหนดว่าง ให้คืนค่า true
เรียก solve() แบบเรียกซ้ำ (recursive) สำหรับโหนดซ้ายและขวา
ถ้าซ้ายหรือขวาคืนค่า false ให้คืนค่า false
ถ้าโหนดซ้ายมีอยู่และค่าต่างจากโหนดปัจจุบัน ให้คืนค่า false
ถ้าโหนดขวามีอยู่และค่าต่างจากโหนดปัจจุบัน ให้คืนค่า false
เพิ่มตัวนับ ret ขึ้น 1
คืนค่า true
ในฟังก์ชันหลัก: ตั้ง ret = 0, เรียก solve(root), คืนค่า ret

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

#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: 
    int ret; 
    bool solve(TreeNode* node){ 
        if (!node || node->val == 0) 
            return true; 
        bool left = solve(node->left); 
        bool right = solve(node->right); 
        if (!left || !right) 
            return false; 
        if (node->left && node->left->val != 0 && node->val != node->left->val) 
            return false; 
        if (node->right && node->right->val != 0 && node->val != node->right->val) 
            return false; 
        ret++; 
        return true; 
    } 
    int countUnivalSubtrees(TreeNode* root){ 
        ret = 0; 
        solve(root); 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {5,1,5,5,5,NULL,5}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.countUnivalSubtrees(root)); 
}

ข้อมูลนำเข้า

{5,1,5,5,5,NULL,5}