Найти сумму кратчайшего корня в путь листа в двоичном дереве

Question

Я пытаюсь реализовать функцию, которая вернет сумму кратчайшего пути в двоичном дереве. Я получаю неправильный ответ 8 вместо 4 для следующего дерева.

         1 
            /\ 
            2 3 
           /\ 
            4 5 

---

int sumOfShortestPath(BinaryTreeNode *root, std::vector<int> vec) { 
if(!root) return 0; 

static int minPathLength = INT_MAX; 
static int pathLength = 0; 
static int sum = 0; 

vec.push_back(root -> data); 
pathLength++; 

if(root -> left == NULL and root -> right == NULL) { 
    if(pathLength < minPathLength){ 
     minPathLength = pathLength; 
     sum = sum_vector(vec); 
     pathLength = 0; 
    } 
} 

sumOfShortestPath(root -> left, vec); 
sumOfShortestPath(root -> right, vec); 

return sum; 
} 

Я считаю, что моя логика верна, но я не уверен, где я буду неправильно. В принципе, если я столкнулся с меньшим путем, я обновляю minPathLength и sum и сбрасываю pathLength обратно в 0 для следующего исследования пути.

Answer 1

Вы как бы на правильном пути, но я думаю, что статические переменные вы можете отключить вас здесь. Кроме того, я не вижу причины сохранять список значений. Вам нужно всего лишь достаточно информации, чтобы определить, являются ли левые или правые ветви кратчайшими.

Вот моя пересмотренная версия:

#include <stdio.h> 

class node 
{ 
public: 
    node *left, *right; 
    int value; 

    node (int v) : left(nullptr), right(nullptr), value(v) { } 
}; 

int sumOfShortestPath(node *root, int *cnt) 
{ 
    if (!root) 
    { 
     *cnt = 0; 
     return 0; 
    } 

    int lcnt; 
    int rcnt; 

    int lsum = sumOfShortestPath(root->left, &lcnt); 
    int rsum = sumOfShortestPath(root->right, &rcnt); 

    if (lcnt < rcnt) 
    { 
     *cnt = lcnt + 1; 
     return root->value + lsum; 
    } 
    else 
    { 
     *cnt = rcnt + 1; 
     return root->value + rsum; 
    } 
} 

node *buildTree() 
{ 
    node *root = new node(1); 

    root->right = new node(3); 

    root->left = new node(2); 
    root->left->left = new node(4); 
    root->left->right = new node(5); 

    return root; 
} 

void main(void) 
{ 
    node *tree = buildTree(); 

    int work = 0; 
    int val = sumOfShortestPath(tree, &work); 

    printf("Result: %d\r\n", val); 
} 

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