Day 48, #116, #120, #123, Populating Next Right Pointers in Each Node, Triangle, Best Time to Buy and Sell Stock II

Populating Next Right Pointers in Each Node
Given a binary tree

    struct TreeLinkNode {
      TreeLinkNode *left;
      TreeLinkNode *right;
      TreeLinkNode *next;
    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

         1
       /  \
      2    3
     / \  / \
    4  5  6  7

After calling your function, the tree should look like:

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

-----------------------------------------------------------------
 typical level order tree traversal, can be implemented with either DFS or BFS
using an array to store the current tailing nodes, one slot for each level

/**
 * 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 traverse (TreeLinkNode* root, int curlevel, vector<TreeLinkNode*>& v) {
        if (root == NULL) {
            return;
        } 
        if (v.size() < curlevel) {
            v.push_back(root);
        }else{
            v[curlevel-1]->next = root;
            v[curlevel-1] = root;
        }
        traverse(root->left,curlevel+1,v);
        traverse(root->right,curlevel+1,v);
    }
    
    void connect(TreeLinkNode *root) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<TreeLinkNode*> v;
        traverse(root,1,v);
    }
};

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 != NULL) {
            TreeLinkNode *pre = root;
            TreeLinkNode *before = NULL;
            while (pre != NULL && pre->left != NULL) {
                if (before != NULL) {
                    before->next = pre->left;
                }
                pre->left->next = pre->right;
                before = pre->right;
                pre = pre->next;
            }
            root = root->left;
        }
    }
};

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
--------------------------------------------
DP in place
replace each element in level #i with the possible minimum sum that are added from level #i+1

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int size = triangle.size();
        for (int row = size - 2; row >= 0; row--) {
            for (int index = 0; index < triangle[row].size(); index++) {
                triangle[row][index] += min(triangle[row+1][index],triangle[row+1][index+1]);
            }
        }
        return triangle[0][0];
    }
};

Best Time to Buy and Sell Stock II
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 as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
-----------------------------------------------------------------------
greedy

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int sum = 0;
        for (int i = 1; i < prices.size(); i++) {
            int dif = prices[i] - prices[i - 1];
            if (dif > 0) {
                sum += dif;
            }
        }
        return sum;
    }
};