Tổng đường đi lớn nhất trong cây nhị phân trong C++

Trong bài toán này, chúng ta được cho một cây nhị phân với mỗi nút chứa một giá trị. Nhiệm vụ là viết chương trình tìm tổng đường đi lớn nhất giữa hai nút lá của cây nhị phân.

Định nghĩa

Cây nhị phân là cấu trúc dữ liệu cây mà mỗi nút có tối đa hai nút con: nút con trái và nút con phải.

Chúng ta cần tìm đường đi từ nút lá này đến nút lá khác cho tổng giá trị lớn nhất. Đường đi này có thể đi qua gốc hoặc không.

Ví dụ minh họa

Đầu ra: 24

Giải thích: Đường đi từ nút lá 2 đến nút lá 9 cho tổng lớn nhất: (2 + 5 + 6 - 2 + 4 + 9) = 24

Phương pháp giải

Thực hiện duyệt cây và lưu trữ tổng lớn nhất cho cây con trái/cây con phải của nút hiện tại. Đồng thời tìm đường đi lớn nhất giữa hai nút lá cho đến thời điểm hiện tại.

Với mỗi nút, tìm đường đi lá-đến-lá lớn nhất cho các cây con của nó. Sau đó so sánh với tổng đường đi lớn nhất toàn cục và lưu giá trị lớn hơn.

Chương trình C++

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

struct Node {
    int data;
    struct Node* left, *right;
};

struct Node* insertNode(int data) {
    struct Node* node = new(struct Node);
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}

int max(int a, int b) { return (a >= b) ? a : b; }

int maxPathSumLeaf(struct Node *root, int &maxSum) {
    if (root == NULL) return 0;
    if (!root->left && !root->right) return root->data;
    
    int leftSubTree = maxPathSumLeaf(root->left, maxSum);
    int rightSubTree = maxPathSumLeaf(root->right, maxSum);
    
    if (root->left && root->right) {
        maxSum = max(maxSum, leftSubTree + rightSubTree + root->data);
        return max(leftSubTree, rightSubTree) + root->data;
    }
    return (!root->left) ? rightSubTree + root->data : leftSubTree + root->data;
}

int main() {
    struct Node *root = insertNode(-2);
    root->left = insertNode(6);
    root->right = insertNode(4);
    root->left->left = insertNode(5);
    root->left->right = insertNode(1);
    root->left->left->left = insertNode(2);
    root->left->left->right = insertNode(-1);
    root->left->right->left = insertNode(-3);
    root->left->right->left->left = insertNode(7);
    root->right->left = insertNode(9);
    root->right->right = insertNode(3);
    
    int maxSum = INT_MIN;
    maxPathSumLeaf(root, maxSum);
    cout << "Max pathSum of between two leaf nodes for the given binary tree is " << maxSum;
    return 0;
}

Kết quả

Max pathSum of between two leaf nodes for the given binary tree is 24