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.