binary_tree_max_sum.md

Максимальная сумма значений ветки дерева

Условие

Дано бинарное дерево, каждая вершина которого это:

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
}

Требуется написать метод, который найдет максимальную сумму значений ветки. На вход подается корень бинарного дерева. Метод должен вернуть целое число - максимальную сумму значений ветки бинарного дерева.

Решение

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public static int maxSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return root.value + Math.max(sum(root.left), sum(root.right));
    }
}

При работе с бинарными деревьями и подсчете их высоты, основная идея заключается в использовании рекурсии.

Идея в том, чтобы "посчитать" сумму значений каждой ветки, а после взять наибольшую.