Đếm nút cây hoàn chỉnh trong C++

Giả sử chúng ta có một cây nhị phân hoàn chỉnh, chúng ta phải đếm số lượng nút. Vì vậy, nếu cây như sau:

Đầu ra sẽ là 6.

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

Điều này sẽ sử dụng cách tiếp cận đệ quy. Phương thức countNodes() nhận gốc làm tham số.
hr := 0 và hl := 0
Tạo hai nút l và r là gốc
khi l không rỗng
- tăng hl lên 1
- l := trái của l
khi r không rỗng
- r := phải của r
- tăng hr lên 1
nếu hl = hr, thì trả về (2 ^ hl) – 1
trả về 1 + countNodes(trái của gốc) + countNodes(phải của gốc)

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

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = 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 fastPow(int base, int power){
        int res = 1;
        while(power > 0){
            if(power & 1) res *= base;
            base *= base;
            power >>= 1;
        }
        return res;
    }
    int countNodes(TreeNode* root) {
        int hr = 0;
        int hl = 0;
        TreeNode* l = root;
        TreeNode* r = root;
        while(l){
            hl++;
            l = l->left;
        }
        while(r){
            r = r->right;
            hr++;
        }
        if(hl == hr) return fastPow(2, hl) - 1;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8,9,10};
    TreeNode *node = make_tree(v);
    cout << (ob.countNodes(node));
}

Đầu vào

[1,2,3,4,5,6,7,8,9,10]