Chương trình tìm tổng các lá bên phải của cây nhị phân trong C++

Giả sử có một cây nhị phân, ta phải tìm tổng tất cả các lá bên phải trong cây nhị phân cho trước.

Vì vậy, nếu đầu vào như:

thì kết quả sẽ là 17, vì có hai lá bên phải trong cây nhị phân, với giá trị 7 và 10 tương ứng.

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

• Định nghĩa hàm dfs(), nhận nút, add,
• nếu nút null, thì trả về
• nếu left và right của nút đều null và add khác 0, thì ret := ret + giá trị nút
• dfs(left của nút, false)
• dfs(right của nút, true)
• Từ phương thức chính, làm: ret := 0, dfs(root, true), trả về ret

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

int main() {
    Solution ob;
    TreeNode *root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(15);
    root->left->right = new TreeNode(7);
    cout << (ob.solve(root));
    return 0;
}

Đầu vào

TreeNode *root = new TreeNode(3); root->left = new TreeNode(9); root->right = new TreeNode(10); root->left->left = new TreeNode(15); root->left->right = new TreeNode(7);

Đầu ra

17