Найти максимальную длину пути только с 1

Question

У меня есть дерево, состоящее только из двоичных чисел как данные узла. Теперь я должен найти максимальную длину пути, состоящую только из узлов, у которых значение своего узла равно 1, и путь должен быть непрерывным, т. Е. Он не должен содержать никакого нуля на своем пути.

Например, давайте рассмотрим это дерево:

root->data = 0; 
root->left->data = 1; 
root->right->data = 0; 
root->left->left->data = 1; 
root->left->right->data = 1; 
root->left->left->left->data = 1; 
root->left->right->left->data = 1; 
root->left->right->right->data = 0; 

Ответ выше дерева должно быть 5. Пожалуйста, обратитесь к рисунку в ссылке ниже:

Click this for more detail

Как может Я делаю это?

Answer 1

Алгоритм может быть следующее (псевдокод):

maxPath tree | treeHasNoChildren = []    
      | data == 0 = [] 
      | otherwise = 
       takeSolutionHavingMaxLength (
        left:maxPath (left tree), 
        right:maxPath (right tree) 
       ) 

Answer 2

Основная идея:

int GetDepthWithCondition(Node node) 
{ 
    if (node.Data == 0) 
     return -100000; 
    return 1 + Math.Max(GetDepthWithCondition(node.RightSon), 
         GetDepthWithCondition(node.LeftSon)); 
} 

Answer 3

Ваш пример странно. Я не понимаю, как ответ равен 5, когда ваш корень имеет 0, он должен быть равен 0. Кроме того, это должно быть только 4, поскольку самый длинный путь по всей левой стороне, если корень равен 1.

в любом случае, это, по существу, найти высоту дерева, вынуждая значения быть 1. это вариант на diameter of a binary tree, который может быть реализован путем модификации базового решения, как это:

public int MaxDiameterWithOnes(Node node) 
{ 
    if (node == null || node.Data == 0) 
     return 0; 
    return 1 + Math.Max(MaxDiameterWithOnes(node.Left), MaxDiameterWithOnes(node.Right)); 
} 

Вы можете изменить это с помощью второй метод в ссылке выше, чтобы быть более эффективным.