c - 查找二叉树中最短根到叶路径的总和

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

可能有比这更优化的计算树长度的方法，但这最终可以完成工作。