如何找到二叉树中的最小路径和并打印路径?该路径可以是从 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/