Chương trình tìm tổng các nút sâu nhất trong C++

Giả sử có một cây nhị phân; ta phải tìm tổng giá trị các lá sâu nhất. Nếu cây như sau:

Thì kết quả sẽ là 11.

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

• Định nghĩa map m và maxDepth
• Định nghĩa phương pháp đệ quy solve(), nhận nút và level, ban đầu level là 0
• nếu nút không có, trả về
• maxDepth := max của level và maxDepth
• tăng m[level] thêm giá trị nút
• solve(left của nút, level + 1)
• solve(right của nút, level + 1)
• Trong phương thức chính, thiết lập maxDepth := 0, rồi solve(root, 0)
• trả về m[maxDepth]

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 = NULL;
        right = NULL;
    }
};

class Solution {
public:
    int maxDepth;
    map<int, int> m;
    void solve(TreeNode* node, int level = 0) {
        if(!node) return;
        maxDepth = max(level, maxDepth);
        m[level] += node->val;
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    int deepestLeavesSum(TreeNode* root) {
        maxDepth = 0;
        m.clear();
        solve(root);
        return m[maxDepth];
    }
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->right->right->right = new TreeNode(4);
    root->left->left->left = new TreeNode(7);
    Solution ob;
    cout << (ob.deepestLeavesSum(root));
    return 0;
}

Đầu vào

TreeNode *root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->right->right = new TreeNode(6); root->right->right->right = new TreeNode(4); root->left->left->left = new TreeNode(7);

Đầu ra

11