class Solution {
public:
    int sumNumbers(TreeNode* root) {
        if (root == NULL) return 0;
        int ret = 0;
        int currentSum = 0;
        this->sumLeafNode(root, ret, currentSum);
        return ret;
    }
    
    void sumLeafNode(TreeNode* root, int& ret, int& currentSum) {
        if (root == NULL) return;
        currentSum = currentSum * 10 + root->val;
        if (root->left == NULL && root->right == NULL) ret += currentSum;
        this->sumLeafNode(root->left, ret, currentSum);
        this->sumLeafNode(root->right, ret, currentSum);
        currentSum = currentSum / 10;
    }
};

/**
 * 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 maxPathSum(TreeNode* root) {
        int max = -10000;
        this->findPath(root, max);
        return max;
    }
    
    int findPath(TreeNode* root, int& max) {
        if (root == NULL) return -100000;
        int left = this->findPath(root->left, max);
        if (left > max) max = left;
        int right = this->findPath(root->right, max);
        if (right > max) max = right;
        int cur = root->val + (left >= 0 ? left : 0) + (right >= 0 ? right : 0);
        if (cur > max) max = cur;
        
        int bias = 0;
        if (left > 0) bias = left;
        if (right > 0  && right > left) bias = right;
        return root->val + bias;
    }
};

/**
 * 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) {
        if (root == NULL) return;
        TreeLinkNode* cur = root;
        while(cur != NULL) {
            cur = this->linkSameLayer(cur);
        }
    }
    
    TreeLinkNode* linkSameLayer(TreeLinkNode* parent) {
        TreeLinkNode* traverse = parent->left;
        if (traverse == NULL) return NULL;
        
        TreeLinkNode* ret = traverse;
        int count = 0;
        while (parent != NULL) {
            traverse->next = count % 2 ? parent->left : parent->right;
            traverse = traverse->next;
            parent = count % 2 ? parent : parent->next;
            count += 1;
        }
        return ret;
    }
};

class Solution {
public:
    string getPermutation(int n, int k) {
        vector<int> total = this->sumTotalList(n);
        vector<int> remains_digits;
        string ret(n, 'a');
        for (int i = 1; i <= n; i++){
            remains_digits.push_back(i);
        }
        
        int index = n - 1;
        int remain = 0;
        int count = n;
        
        while (index >= 0){
            int target_index = count * (k - 1) / total[index];
            int target = remains_digits[target_index];
            remains_digits.erase(remains_digits.begin() + target_index);
            ret[n - 1 - index] = '0' + target;
            k -= total[index - 1] * target_index;
            index -= 1;
            count -= 1;
        }
        return ret;
    }
    
    vector<int> sumTotalList(int n) {
        vector<int> ret(1, 1);
        if (n == 0 || n == 1) return ret;
        int index = 2;
        int sum = 1;
        while (index <= n){
            sum *= index;
            ret.push_back(sum);
            index += 1;
        }
        return ret;
    }
};

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class BSTIterator {
public:
    BSTIterator(TreeNode *root) {
        this->nodeStack = new stack<TreeNode*>();
        this->current = root;
        while(this->current != NULL) {
            this->nodeStack->push(this->current);
            this->current = this->current->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !this->nodeStack->empty();
    }

    /** @return the next smallest number */
    int next() {
        this->current = this->nodeStack->top();
        this->nodeStack->pop();
        int ret = this->current->val;
        
        this->current = this->current->right;
        while(this->current != NULL) {
            this->nodeStack->push(this->current);
            this->current = this->current->left;
        }
        return ret;
    }
private:
    TreeNode* current;
    stack<TreeNode*>* nodeStack;
};

/**
 * Your BSTIterator will be called like this:
 * BSTIterator i = BSTIterator(root);
 * while (i.hasNext()) cout << i.next();
 */