バイナリツリーの最短ルートからリーフパスの合計を求める

Question

私はバイナリツリーの最短パスの合計を返す関数を実装しようとしています。私は次のツリーに対して4の代わりに8という誤った答えを得ています。

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

があり、これよりも木の長さをカウントする、おそらくはるかに最適な方法がありますが、これは一日の終わりに仕事を取得します。