Skip to content

3.30.2017(Q90-Q120).md

Latest commit

 

History

History
944 lines (883 loc) · 25.8 KB

3.30.2017(Q90-Q120).md

File metadata and controls

944 lines (883 loc) · 25.8 KB

Questions 91 ~ 120

Full score: 6 X 100 = 600
Actual score:

91, Decode Ways

Questions: A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' to 1...
Idea: dfs + dp;
class Solution {
    vector<int> dp;
    int nDec(string &s, int i){
        if(i==s.size()) return 1;
        if(i==s.size()-1) return s[s.size()-1] !='0';
        if(dp[i]>=0) return dp[i];
        int x = int(s[i]-'0'), y = int(s[i+1]-'0');
        return dp[i] = int(x!=0)*(nDec(s,i+1) + int(x*10+y<=26)*nDec(s,i+2));
    }
public:
    int numDecodings(string s) {
        if(s.empty()) return 0;
        dp = vector<int>(s.size(),-1);
        return nDec(s,0);
    }
};

92, Reverse Linked List II

Questions: Reverse a linked list from position m to n. Do it in-place and in one-pass. For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Idea: One pass doing the job:
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if(!head || !head->next || m==n) return head;
        ListNode preHead(0);
        preHead.next = head;
        auto p = &preHead;
        for(int i=1;i<m;++i) p = p->next;
        auto p1 = p->next, pt = p->next;
        auto p2 = p1->next;
        for(int i=m;i<n && p2;i++){
            auto tmp = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = tmp;
        }
        pt->next = p2;
        p->next = p1;
        return preHead.next;
    }
};

93, Restore IP Addresses

Questions: Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example: Given "25525511135", return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
Idea: dfs (Need to care about the special case when s[i]=='0')
typedef vector<int> vi;
class Solution {
    void help(vector<vi> &res,vi cur, string &s, int i, int k){
        if(k==4){
            if(i==s.size()) res.push_back(cur);
            return;
        }
        if(i==s.size()) return;
        if(s[i] == '0'){
            cur.push_back(0);
            help(res,cur,s,i+1,k+1);
            return;
        }
        for(int j=i+1;j<=s.size();j++){
            int m = stoi(s.substr(i,j-i));
            if(m>255) return;
            cur.push_back(m);
            help(res,cur,s,j,k+1);
            cur.pop_back();
        }
        return;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        vector<vi> res;
        help(res,vi(),s,0,0);
        vector<string> ans;
        for(auto vec:res){
            s = to_string(vec[0]);
            s += "." + to_string(vec[1]) + "." + to_string(vec[2]) + "." + to_string(vec[3]);
            ans.push_back(s);
        }
        return ans;
    }
};

94, Binary Tree Inorder Traversal

Questions: Given a binary tree, return the inorder traversal of its nodes' values. (left -> root -> right)
Idea: using stack //Take care the forever loop
/**
 * 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:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode *> S;
        while(root || !S.empty()){
            while(root){
                S.push(root);
                root=root->left;
            }
            if(!S.empty()){
                ans.push_back(S.top()->val);
                root = S.top()->right;
                S.pop();
            }
        }
        return ans;
    }
};

95, Unique Binary Search Trees II

Questions: Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n. For example, Given n = 3, your program should return all 5 unique BST's shown below.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
Idea: using dfs //Note that, every time if we need to add new tree into the set, we need to create a new root instead of the original one.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<TreeNode*> vt;
class Solution {
public:
    vt Creat(int st,int ed){
        if(st>ed) return vt{NULL};
        vt rst;
        for(int i=st;i<=ed;i++){
            vt lvec = Creat(st,i-1),rvec = Creat(i+1,ed);
            for(TreeNode *l1:lvec) for(TreeNode *l2:rvec){
                TreeNode *root = new TreeNode(i);
                root->left = l1;
                root->right = l2;
                rst.push_back(root);
            }
        }
        return rst;
    }
    vector<TreeNode*> generateTrees(int n) {
        if(n==0) return vt();
        return Creat(1,n);
    }
};

96, Unique Binary Search Trees

Questions: Given n, how many structurally unique BST's (binary search trees) that store values 1...n? For example, Given n = 3, your program should return all 5 unique BST's shown below.
   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
Idea: Using dfs (number of unique BST is only depends on the number of node n) //Simple mathematical problem
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1,1);
        for(int k=2;k<=n;++k){
            dp[k] = 0;
            for(int j=1;j<=k;++j) dp[k] += dp[j-1]*dp[k-j];
        }
        return dp[n];
    }
};

97, Interleaving String

Questions: Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. For example, Given: s1 = "aabcc", s2 = "dbbca" When s3 = "aadbbcbcac", return true. When s3 = "aadbbbaccc", return false.
Idea: Using dp //dp[i][j] denote whether s1.substr(0,i) and s2.substr(0,j) are forming s3.substr(0,i+j).
typedef vector<bool> vb;
class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        int n1 = s1.size(), n2 = s2.size(), n3 = s3.size();
        if(n3 != n1+n2) return false;
        map<char,int> cnt;
        for(auto c:s1) cnt[c]++;
        for(auto c:s2) cnt[c]++;
        for(auto c:s3){
            cnt[c]--;
            if(cnt[c]<0) return false;
        }
        cnt.clear();
        vector<vb> dp(n1+1,vb(n2+1,false));
        dp[0][0] = true;
        for(int i=1;i<=n1 && dp[i-1][0];++i) dp[i][0] = s1[i-1]==s3[i-1];
        for(int j=1;j<=n2 && dp[0][j-1];++j) dp[0][j] = s2[j-1]==s3[j-1];
        for(int i=1;i<=n1;++i) for(int j=1;j<=n2;++j){
            dp[i][j] = (dp[i-1][j]&&(s1[i-1]==s3[i+j-1]))||(dp[i][j-1]&&(s2[j-1]==s3[i+j-1]));
        }
        return dp[n1][n2];
    }
};

98, Validate Binary Search Tree

Questions: Given a binary tree, determine if it is a valid binary search tree (BST).
Idea: Easy: just do it.
/**
 * 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:
    bool isValidBST(TreeNode* root) {
        long cur = (long)INT_MIN - 1;
        stack<TreeNode *> S;
        while(root || !S.empty()){
            while(root){
                S.push(root);
                root = root->left;
            }
            if(!S.empty()){
                if(S.top()->val <= cur) return false;
                cur = S.top()->val;
                root = S.top()->right;
                S.pop();
            }
        }
        return true;
    }
};

99, Recover Binary Search Tree

Questions: Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.
Idea: Use inorder to extract the original order, then regain the original valus. //Be careful when regain the original order
/**
 * 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:
    void recoverTree(TreeNode* root) {
        stack<TreeNode *> S;
        vector<TreeNode *> vec;
        vector<int> vals;
        while(root || !S.empty()){
            while(root){
                S.push(root);
                root = root->left;
            }
            if(!S.empty()){
                vec.push_back(S.top());
                vals.push_back(S.top()->val);
                root = S.top()->right;
                S.pop();
            }
        }
        sort(vals.begin(),vals.end());
        for(int i=0;i<vec.size();++i) vec[i]->val = vals[i];
        return;
    }
};

100, Same Tree

Questions: Given two binary trees, write a function to check if they are equal or not.
Idea: recursion is so easy
/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p) return !q;
        if(!q) return false;
        if(p->val != q->val) return false;
        return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
    }
};

101, Symmetric Tree

Questions: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
Idea: Recursion
/**
 * 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 {
    bool isRev(TreeNode *r1,TreeNode *r2){
        if(!r1) return !r2;
        if(!r2) return false;
        if(r1->val != r2->val) return false;
        return isRev(r1->left,r2->right) && isRev(r1->right,r2->left);
    }
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return isRev(root->left,root->right);
    }
};

102, Binary Tree Level Order Traversal

Questions: Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
Idea: recursion
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    void build(vector<vi> &ans,int lvl,TreeNode *rt){
        if(!rt) return;
        if(lvl >= ans.size()) ans.resize(lvl+1);
        ans[lvl].push_back(rt->val);
        build(ans,lvl+1,rt->left);
        build(ans,lvl+1,rt->right);
        return;
    }
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vi> ans;
        build(ans,0,root);
        return ans;
    }
};

103, Binary Tree Zigzag Level Order Traversal

Questions: Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
Idea: The same as the previous one.
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    void build(vector<vi> &ans,int lvl,TreeNode *rt){
        if(!rt) return;
        if(lvl >= ans.size()) ans.resize(lvl+1);
        ans[lvl].push_back(rt->val);
        build(ans,lvl+1,rt->left);
        build(ans,lvl+1,rt->right);
        return;
    }
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vi> ans;
        build(ans,0,root);
        for(int i=1;i<ans.size();i+=2) reverse(ans[i].begin(),ans[i].end());
        return ans;
    }
};

104, Maximum Depth of Binary Tree

Questions: Given a binary tree, find its maximum depth.
Idea: Recursion
/**
 * 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 maxDepth(TreeNode* root) {
        if(!root) return 0;
        return 1 + max(maxDepth(root->left),maxDepth(root->right));
    }
};

105, Construct Binary Tree from Preorder and Inorder Traversal

Questions: Given preorder and inorder traversal of a tree, construct the binary tree.
Idea: Recursion //keep finding root and the range for each child tree //This question is easy since there is no dups
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    TreeNode* BLDG(vi &pre,int pl,int pr,vi &in,int il,int ir){
        if(pl>pr) return NULL;
        int rval = pre[pl];
        int j = il;
        while(j<=ir && in[j]!=rval) ++j;
        TreeNode *root = new TreeNode(rval);
        root->left = BLDG(pre,pl+1,pl+j-il,in,il,j-1);
        root->right = BLDG(pre,pl+j-il+1,pr,in,j+1,ir);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return BLDG(preorder,0,preorder.size()-1,inorder,0,inorder.size()-1);
    }
};

106, Construct Binary Tree from Inorder and Postorder Traversal

Questions: Given inorder and postorder traversal of a tree, construct the binary tree.
Idea: Recursion //keep finding root and the range for each child tree
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    TreeNode* BLDG(vi &pos,int pl,int pr,vi &in,int il,int ir){
        if(pl>pr) return NULL;
        int rval = pos[pr];
        int j = il;
        while(j<=ir && in[j]!=rval) ++j;
        TreeNode *root = new TreeNode(rval);
        root->left = BLDG(pos,pl,pl+j-il-1,in,il,j-1);
        root->right = BLDG(pos,pl+j-il,pr-1,in,j+1,ir);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return BLDG(postorder,0,postorder.size()-1,inorder,0,inorder.size()-1);
    }
};

107, Binary Tree Level Order Traversal II

Questions: Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
Idea: The same as I
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    void build(vector<vi> &ans,int lvl,TreeNode *rt){
        if(!rt) return;
        if(lvl >= ans.size()) ans.resize(lvl+1);
        ans[lvl].push_back(rt->val);
        build(ans,lvl+1,rt->left);
        build(ans,lvl+1,rt->right);
        return;
    }
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vi> ans;
        build(ans,0,root);
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

108, Convert Sorted Array to Binary Search Tree

Questions: Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Idea: Keep finding root, and use recursion
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    TreeNode* bldBST(vi &nums,int l,int r){
        if(l>r) return NULL;
        int j = (l+r)/2;
        TreeNode *root = new TreeNode(nums[j]);
        root->left = bldBST(nums,l,j-1);
        root->right = bldBST(nums,j+1,r);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return bldBST(nums,0,nums.size()-1);
    }
};

109, Convert Sorted List to Binary Search Tree

Questions: Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Idea: The same as the above one
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    TreeNode* bldBST(vi &nums,int l,int r){
        if(l>r) return NULL;
        int j = (l+r)/2;
        TreeNode *root = new TreeNode(nums[j]);
        root->left = bldBST(nums,l,j-1);
        root->right = bldBST(nums,j+1,r);
        return root;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        vi vec;
        for(;head;head=head->next) vec.push_back(head->val);
        return bldBST(vec,0,vec.size()-1);
    }
};

110, Balanced Binary Tree

Questions: Given a binary tree, determine if it is height-balanced.
Idea: Recursion + dp
/**
 * 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 {
    unordered_map<TreeNode *,int> dp;
    int depth(TreeNode * root){
        if(!root) return 0;
        if(dp.count(root)) return dp[root];
        return dp[root] = 1 + max(depth(root->left),depth(root->right));
    }
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        if(abs(depth(root->left)-depth(root->right))>1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
    }
};

111, Minimum Depth of Binary Tree

Questions: Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Idea: Recursion?
/**
 * 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 minDepth(TreeNode* root) {
        if(!root) return 0;
        if(!root->left) return 1 + minDepth(root->right);
        if(!root->right) return 1 + minDepth(root->left);
        return 1 + min(minDepth(root->left),minDepth(root->right));
    }
};

112, Path Sum

Questions: Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
Idea: dfs + dp? ##LeetCode 真无聊
/**
 * 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:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->left && !root->right) return sum==root->val;
        if(root->left && hasPathSum(root->left,sum-root->val)) return true;
        if(root->right && hasPathSum(root->right,sum-root->val)) return true;
        return false;
    }
};

113, Path Sum II

Questions: Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
Idea: dfs
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef vector<int> vi;
class Solution {
    bool isLeaf(TreeNode *root){
        return root&&(!root->left)&&(!root->right);
    }
    void getAns(vector<vi> &ans, vi cur, TreeNode* root, int sum){
        if(!root) return;
        if(isLeaf(root) && root->val==sum){
            cur.push_back(sum);
            ans.push_back(cur);
            return;
        }
        cur.push_back(root->val);
        if(root->left) getAns(ans,cur,root->left,sum-root->val);
        if(root->right) getAns(ans,cur,root->right,sum-root->val);
        return;
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vi> ans;
        getAns(ans,vi(),root,sum);
        return ans;
    }
};

114, Flatten Binary Tree to Linked List

Questions: Given a binary tree, flatten it to a linked list in-place.
Idea: recursion (easy) or stack ##注意边界条件
/**
 * 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:
    void flatten(TreeNode* root) {
        stack<TreeNode *> S;
        while(root){
            if(root->right) S.push(root->right);
            if(root->left) root->right = root->left;
            else if(!S.empty()){
                root->right = S.top();
                S.pop();
            }
            else{
                root->right = NULL;
            }
            root->left = NULL;
            root = root->right;
        }        
    }
};

115, Distinct Subsequences

Questions: Given a string S and a string T, count the number of distinct subsequences of T in S. Here is an example: S = "rabbbit", T = "rabbit", then Return 3.
Idea: dp?
typedef vector<int> vi;
class Solution {
public:
    int numDistinct(string s, string t) {
        int ns = s.size(), nt = t.size();
        if(nt>ns) return 0;
        vector<vi> dp(ns+1,vi(nt,0));
        for(int i=ns-1;i>=0;i--) dp[i][nt-1] = dp[i+1][nt-1] + (s[i]==t[nt-1]);
        for(int j = nt-2;j>=0;j--) for(int i=ns-1;i>=0;--i){
            dp[i][j] = dp[i+1][j];
            if(s[i] == t[j]) dp[i][j] += dp[i+1][j+1];
        }
        return dp[0][0];
    }
};

116, Populating Next Right Pointers in Each Node

Questions: 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.
Idea: Level based travers.
/**
 * 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) return;
        TreeLinkNode *p1=root->left, *p2=root->right;
        while(p1&&p2){
            p1->next = p2;
            p1 = p1->right;
            p2 = p2->left;
        }
        connect(root->left);
        connect(root->right);
        return;
    }
};

117, Populating Next Right Pointers in Each Node II

Questions: 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?
Idea: Level based travers.
/**
 * 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 {
    void LBT(vector<vector<TreeLinkNode *>> &ans, TreeLinkNode *root, int lvl){
        if(!root) return;
        if(lvl >= ans.size()) ans.resize(lvl+1);
        ans[lvl].push_back(root);
        LBT(ans,root->left,lvl+1);
        LBT(ans,root->right,lvl+1);
    }
public:
    void connect(TreeLinkNode *root) {
        vector<vector<TreeLinkNode *>> ans;
        LBT(ans,root,0);
        for(int i=0;i<ans.size();++i) for(int j=0;j<ans[i].size();++j){
            if(j<ans[i].size()-1) ans[i][j]->next = ans[i][j+1];
            else ans[i][j]->next = NULL;
        }
    }
};

118, Pascal's Triangle

Questions: Given numRows, generate the first numRows of Pascal's triangle.
Idea: Just Do It
typedef vector<int> vi;
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for(int k=1;k<=numRows;++k){
            ans.push_back(vi(k,1));
            for(int i=1;i<k-1;++i) ans[k-1][i] = ans[k-2][i-1] + ans[k-2][i];
        }
        return ans;
    }
};

119, Pascal's Triangle II

Questions: Given an index k, return the kth row of the Pascal's triangle.
Idea: Just Do It
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans;
        for(int k=0;k<=rowIndex;++k){
            vector<int> tmp(k+1,1);
            for(int i=1;i<k;++i) tmp[i] = ans[i-1]+ans[i];
            ans.swap(tmp);
        }
        return ans;
    }
};

120, Triangle

Questions: Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
Idea: Easy DP；
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        if(!n) return 0;
        vector<int> dp(triangle[n-1].begin(),triangle[n-1].end());
        for(int j=n-2;j>=0;--j){
            vector<int> tmp(triangle[j].begin(),triangle[j].end());
            for(int i=0;i<tmp.size();++i) tmp[i] += min(dp[i],dp[i+1]);
            dp.swap(tmp);
        }
        return dp[0];
    }
};