c++ - 二叉树中的最小路径总和

如何在二叉树中找到最小路径总和并打印路径？路径可以是从ROOT节点到任何LEAF节点的路径。我已经编写了C++代码来找到最小和，但是在打印路径时遇到了问题。

int MinTreePathSum(TreeNode *head, vector<TreeNode> &path)
{
    if(!head)  // head is NULL
        return 0;
    else if(!(head->left) && head->right)  // only head->left is NULL
        return head->val+MinTreePathSum(head->right, path);
    else if(!(head->right) && head->left)  // only head->right is NULL
        return head->val+MinTreePathSum(head->left, path);
    else
        return head->val+min(MinTreePathSum(head->left, path), MinTreePathSum(head->right, path));  // none of left and right are NULL
}

不使用参数列表中的path，有人可以帮我打印路径总和最小的路径吗？

最佳答案

代替return head->val+min(MinTreePathSum(head->left, path), MinTreePathSum(head->right, path));，检查左右路径中的哪一个是最小的。通过保存它们，您可以找到路径。

int MinTreePathSum(TreeNode *head, string &path)
{
    if(!head)  // head is NULL
        return 0;
    else if(!(head->left) && head->right)  // only head->left is NULL
    {
        string p;
        int val = head->val+MinTreePathSum(head->right, p);
        path = "R" + p;
        return val;
    }
    else if(!(head->right) && head->left)  // only head->right is NULL
    {
        string p;
        int val = head->val+MinTreePathSum(head->left, p);
        path = "L" + p;
        return val;
    }
    else
    {
        int vl,vr,val;
        string pl,pr;
        vl = MinTreePathSum(head->left, pl);
        vr = MinTreePathSum(head->right, pr);
        if ( vl < vr ){
             val = vl;
             path = "L" + pl;
        } else {
             val = vr;
             path = "R" + pr;
        }
        return head->val + val;
    }
}

关于c++ - 二叉树中的最小路径总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34233675/