It's a follow up of LC 124, the interviewer wants to print out the path which has the maximum path sum, anyone has any ideas?
Facebook interview question: Print out the path which has the maximum path sum of a binary tree

@younghobbits maybe we could first find the "root" of the maximum path sum, and compute the sums of the nodes in its subtrees. Then start from the "root" recover the maximum path.

@milu Emmm..I'm not sure I understand your solution, the "root" you mean is it the root which the maximum path passing through? Why do we need to compute the sums and how to recover the maximum path? I think maybe this can be solved by adding nodes in a vector during the traverse of finding max path, but I didn't figure out how to maintain the vectors..

@younghobbits Yeah, the "root" is the root of the maixmum path sum.
Suppose, we know the "root" of the maximum path sum. How do we recover the path?
Starting from the "root", we check the left subtree (root>left
) first, then print the currentroot>val
, then check the right subtree.
Now suppose we have computed all the sums of the nodes in the subtrees and stored these sums in theval
member (the original values can be restored if needed). For the left subtree, ifroot>left>val <= 0
, we could just return. Otherwise, we check the two children ofroot>left
and choose the child with positive and larger sum. I have this ugly code below:class Solution { struct PathInfo { int maxpath = 0, path = 0; // maxpath is the max path, path is the max path starting from the current node, path is not negative // now try to print out the path with maximum path sum // record the LCA TreeNode *lca; }; PathInfo helper(TreeNode *root) { if (!root) return {INT_MIN, 0, NULL}; PathInfo ans; PathInfo leftret = helper(root>left); PathInfo rightret = helper(root>right); ans.path = max(0, max(leftret.path, rightret.path) + root>val); ans.maxpath = max(leftret.path + rightret.path + root>val, max(leftret.maxpath, rightret.maxpath)); if (leftret.path + rightret.path + root>val >= max(leftret.maxpath, rightret.maxpath)) { ans.lca = root; } else if (leftret.maxpath >= rightret.maxpath) { ans.lca = leftret.lca; } else { ans.lca = rightret.lca; } return ans; } void printhelper(TreeNode *node, bool isLeft) { if (!node  node>val <= 0) return; // recover the node>val and store it in 'val' int val = node>val; if (!node>left) { if (node>right && node>right>val > 0) val = node>right>val; } else if (!node>right) { if (node>left && node>left>val > 0) val = node>left>val; } else if (max(node>left>val, node>right>val) > 0) val = max(node>left>val, node>right>val); // if it's on the right side of the "root" (of the maximum path sum), print 'val' first if (!isLeft) cout << val << ", "; // print the maximum of left and right path if (!node>left) printhelper(node>right, isLeft); else if (!node>right) printhelper(node>left, isLeft); else { if (node>left>val > node>right>val) printhelper(node>left, isLeft); else printhelper(node>right, isLeft); } if (isLeft) cout << val << ", "; return; } void printPath(TreeNode *root) { printhelper(root>left, true); cout << root>val << ", "; printhelper(root>right, false); } int computesums(TreeNode *root) { if (!root) return 0; int leftsum = computesums(root>left); int rightsum = computesums(root>right); int tmp = max(leftsum, rightsum); if (tmp > 0) { root>val += tmp; } return root>val; } public: int maxPathSum(TreeNode* root) { // return helper(root).maxpath; PathInfo ans = helper(root); computesums(ans.lca>left); computesums(ans.lca>right); printPath(ans.lca); return ans.maxpath; } };
Hope someone could come up with a better and cleaner solution.

@milu Hi milu, thanks for your code and explaining, I got the idea. However, I was thinking if we can name a struct to store the node's height and the current maximum path, then do a post order traversal, to update the current node's height and path information according to its left child and right child. Here is my code, I tried a several cases are good but I don't know if I left some corner cases..
pathInfo printDiameter(TreeNode* root){ if(!root) return pathInfo(0,0); pathInfo left = printDiameter(root>left); pathInfo right = printDiameter(root>right); // post order traversal pathInfo cur(0,0); int leftHeight = max(left.curHeight,0); int rightHeight = max(right.curHeight,0); cur.curHeight = max(leftHeight,rightHeight)+root>val; if(cur.curHeight == left.curHeight+root>val) cur.heightList = left.heightList; else if(cur.curHeight == right.curHeight+root>val) cur.heightList = right.heightList; cur.heightList.push_back(root>val); // it would directly reach here if leftHeight and rightHeight is 0 cur.maxPath = max(max(left.maxPath,right.maxPath),leftHeight+rightHeight+root>val); if(cur.maxPath == left.maxPath){ cur.pathList = left.pathList; } else if(cur.maxPath == right.maxPath){ cur.pathList = right.pathList; } else { if(!leftHeight && !rightHeight) cur.pathList.push_back(root>val); else if(!leftHeight  !rightHeight){ cur.pathList = leftHeight ? left.heightList : right.heightList; cur.pathList.push_back(root>val); } else{ cur.pathList = left.heightList; cur.pathList.insert(cur.pathList.end(), right.heightList.begin(), right.heightList.end()); cur.pathList.push_back(root>val); } } return cur; }

@younghobbits Hi, I think the basic idea should work, but your code may fail if there are negative values in the tree.
You may want to change toif (!root) return pathInfo(INT_MIN, 0);
.
There is an invariant I maintained in my original code, which isthe max path starting from the current node
(path
in my code,curHeight
in yours?) is nonnegative. So I would changecur.curHeight = max(leftHeight, rightHeight) + root>val
tocur.curHeight = max(0, max(left.curHeight, right.curHeight)+root>val)
.
It'll also be easier to understand your code if you could provide thepathInfo
struct with comments.
