İkili bir ağaçta yaprak yoluna en kısa kök toplamını bul

Question

İkili bir ağaçta en kısa yolun toplamını döndürecek bir işlev uygulamaya çalışıyorum. Aşağıdaki ağaç için 4 yerine 8 yanlış cevap alıyorum.

---

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; 
} 

         1 
            /\ 
            2 3 
           /\ 
            4 5 

benim mantık doğru olduğuna inanıyoruz ama ben yanlış nereye gidiyorum ben emin değilim. Temel olarak, daha küçük bir yolla karşılaşırsam, minPathLength ve sum'u güncelleştirir ve pathLength'u bir sonraki yol araştırması için 0'a döndürürüm.

Answer 1

Doğru yoldasınız, ama statik değişkenlerin sizi buraya getirdiğini düşünüyorum. Ayrıca, değerlerin bir listesini tutmak için bir neden göremiyorum. Sol veya sağ dalların en kısa olup olmadığını belirlemek için sadece yeterli bilgiye ihtiyacınız vardır.

İşte benim revize edilmiş versiyonu var:

#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); 
} 

Orada bundan daha ağaç uzunlukları sayma muhtemelen çok daha optimum yolu vardır, ancak bu günün sonunda işi alır.