Facebook interview question: Print out the path which has the maximum path sum of a binary tree


  • 0

    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?


  • 0
    M

    @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.


  • 0

    @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..


  • 0
    M

    @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 current root->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 the val member (the original values can be restored if needed). For the left subtree, if root->left->val <= 0, we could just return. Otherwise, we check the two children of root->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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.