Very Short Codes, One Time Recursion


  • 0
    B

    Variables with 'single' mean paths have no branches( viz, there are no nodes with two children in the path), variables with 'passed' mean paths cover the current tree node.

    class Solution {
    public:
        void maxPathSum_recur(TreeNode *cur, int &single, int &passed, int &ans)
        {
            if(cur == NULL)
            {
                single = 0;
                passed = 0;
                return;
            }
            int singleLeft, singleRight, childPassed;
            maxPathSum_recur(cur->left, singleLeft, childPassed, ans);
            maxPathSum_recur(cur->right, singleRight, childPassed, ans);
            int tmp = max(singleLeft, singleRight);
            single = (tmp>0?tmp:0) + cur->val;
            passed = max(singleLeft + singleRight + cur->val, single);
            if(passed > ans)ans = passed;
        }
        int maxPathSum(TreeNode *root) {
            if(root == NULL)return 0;
            int ans = root->val, single, passed;
            maxPathSum_recur(root, single, passed, ans);
            return ans;
        }
    };

Log in to reply
 

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