Min Path Sum in a Binary Tree

1
votes

How to find the minimum path sum in a binary tree, and print the path? The path can be from ROOT node to any LEAF node. I have written the C++ code to find the min sum, but have problems in printing the path.

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
}

The path in the argument list is not used, could anyone help me to print the path which has the minimum path sum?

2
c++algorithmrecursionbinary-tree
1) Do you want to update the path ? 2) Is it on purpose that you use vector<TreeNode> instead of vector<TreeNode*> ? – Christophe
1) The path vector is initially with size = 0, it is used to store the qualified TreeNode. 2) I think we can do either way, as long as the path is uniquely determined. – Liang Li
@Christophe I just realized using vector<TreeNode *> is much better than vector<TreeNode>. Forget about my previous answer 2) – Liang Li

2 Answers

2
votes

Instead of return head->val+min(MinTreePathSum(head->left, path), MinTreePathSum(head->right, path)); check which one of the right or left path is the minimum. By saving them you can find the 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;
    }
}
2
votes

I think you are really close... just add the current node to path and choose shortest path if current node has two children:

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
        path.push(*head);
        return head->val+MinTreePathSum(head->right, path);
    }else if(!(head->right) && head->left) { // only head->right is NULL
        path.push(*head);
        return head->val+MinTreePathSum(head->left, path);
    }else{ // two children, must choose one...
        path.push(*head);

        // get left and right paths
        pathLeft = vector<TreeNode>(); 
        pathRight = vector<TreeNode>();
        int valLeft = MinTreePathSum(head->left, pathLeft);
        int valRight = MinTreePathSum(head->right, pathRight);

        // actually copy the shortest path
        if (valLeft < valRight) {
            for(int i = 0; i < pathLeft.size(); ++i) {
                path.push(pathLeft[i]);
            }
        }else{
            for(int i = 0; i < pathRight.size(); ++i) {
                path.push(pathRight[i]);
            }
        }  
        // finally return the minimum path, which is the one we put in "path" already
        return head->val + min(valLeft, valRight);
    }
}