Day 67, #117, #123, #124, Populating Next Right Pointers in Each Node II, Best Time to Buy and Sell Stock III, Binary Tree Maximum Path Sum

Populating Next Right Pointers in Each Node II
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:

• You may only use constant extra space.

For example,
Given the following binary tree,

         1
       /  \
      2    3
     / \    \
    4   5    7

After calling your function, the tree should look like:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \    \
    4-> 5 -> 7 -> NULL

-----------------------------------------------------------------------
Same exact solution to #116 Populating Next Right Pointers in Each Nod

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void travese (TreeLinkNode* root, vector<TreeLinkNode*> &tails, int level) {
        if (root == NULL) {
            return;
        }
        if (tails.size() < level) {
            tails.push_back(root);
        }else {
            tails[level - 1]->next = root;
            tails[level - 1] = root;
        }
        travese(root->left,tails,level + 1);
        travese(root->right,tails,level + 1);
    }

    void connect(TreeLinkNode *root) {
        vector<TreeLinkNode*> tails;
        travese(root,tails,1);
    }
};

Update Feb-19-2015
constant space

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        while (root) {
            TreeLinkNode *cur = root, *pre = NULL, *nextLevel = NULL;
            
            while (cur) {
                if (cur->left != NULL) {
                    if (nextLevel == NULL) nextLevel = cur->left;
                    if (pre == NULL) pre = cur->left;
                    else {
                        pre->next = cur->left;
                        pre = cur->left;
                    }
                }
                
                if (cur->right != NULL) {
                    if (nextLevel == NULL) nextLevel = cur->right;
                    if (pre == NULL) pre = cur->right;
                    else {
                        pre->next = cur->right;
                        pre = cur->right;
                    }
                }
                
                cur = cur->next;
            }
            root = nextLevel;
        }
    }
};

Best Time to Buy and Sell Stock III
Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
------------------------------------------------------------------------------------------
DP
Divide prices[] in two parts, each which is solved as in #121 Best Time to Buy and Sell Stock
the max profit would be the largest value of  firstPart[i] + secondPart[i]

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0) return 0;
        vector<int> dp1(prices.size(),0);
        vector<int> dp2 = dp1;
        
        int minimun = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp1[i] = max(dp1[i - 1], prices[i] - minimun);
            minimun = min(prices[i],minimun);
        }
        
        int maximum = prices.back();
        for (int i = prices.size() - 2; i >= 0; i--) {
            dp2[i] = max(dp2[i + 1], maximum - prices[i]);
            maximum = max(prices[i],maximum);
        }
        
        int maxProfit = 0;
        for (int i = 0; i < prices.size(); i++) {
            maxProfit = max(dp1[i] + dp2[i],maxProfit);
        }
        return maxProfit;
    }
};

Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.
--------------------------------------------------------------------------
Two scenarios:
1) Current node is the root(top) node of the path
2) Current node is in either left or right sub-tree of the path
Hence, according to the 1st, we have to include the sum of both left and right sub-trees when we calculate maximum. In another word, we produce its maximum value for each node in binary tree. But according to the 2nd, return back to upper level in recursive stack with only one or non of sub-trees.  

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode *root,int &maximumPath) {
        if (root == NULL) {
            return INT_MIN;
        }
        
        int leftSum = max(0,pathSum(root->left,maximumPath));
        int rightSum = max(pathSum(root->right,maximumPath),0);
        
        maximumPath = max(maximumPath,leftSum + rightSum + root->val);
        return max(leftSum,rightSum) + root->val;
    }

    int maxPathSum(TreeNode* root) {
        int m = INT_MIN;
        pathSum(root,m);
        return m;
    }
};

另一种写法

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int helper(TreeNode *root,int *sum) {
        if  (root == NULL) {
            *sum = 0;
            return INT_MIN;
        }
        
        int ls = 0, rs = 0;
        int leftM = helper(root->left,&ls);
        int rightM = helper(root->right,&rs);
        
        ls = max(ls,0);
        rs = max(rs,0);
        *sum = max(ls,rs) + root->val;
        
        return max(ls + rs + root->val, max(leftM,rightM));
    }


    int maxPathSum(TreeNode* root) {
        int sum = 0;
        return helper(root,&sum);
    }
};