Day 66, #103, #115, Binary Tree Zigzag Level Order Traversal, Distinct Subsequences

Binary Tree Zigzag Level Order Traversal
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).
For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

----------------------------------------------------------------------
Similar to #102 Binary Tree Level Order Traversal

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int> > ret;
    
    void stackOrder2 (vector<int>& level, stack<TreeNode*>& cur, stack<TreeNode*>& next) {
        while (!cur.empty()) {
            TreeNode* node = cur.top();
            cur.pop();
            level.push_back(node->val);
            if (node->right != NULL) {
                next.push(node->right);
            }
            if (node->left != NULL) {
                next.push(node->left);
            }
        }
    }

    void stackOrder1 (vector<int>& level, stack<TreeNode*>& cur, stack<TreeNode*>& next) {
        while (!cur.empty()) {
            TreeNode* node = cur.top();
            cur.pop();
            level.push_back(node->val);
            if (node->left != NULL) {
                next.push(node->left);
            }
            if (node->right != NULL) {
                next.push(node->right);
            }
        }
    }

    vector<vector<int> > zigzagLevelOrder(TreeNode *root) {
        stack<TreeNode*> st1, st2;
        if (root == NULL) return ret;
        int levelCount = 0;
        st1.push(root);
        while (!st1.empty() || !st2.empty()) {
            vector<int> level;
            if (levelCount % 2 == 0) {
                stackOrder1(level,st1,st2);
            }else {
                stackOrder2(level,st2,st1);
            }
            ret.push_back(level);
            levelCount++;
        }
        return ret;
    }
};

更新，Sep-10-2015

/**
 * 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> zig(vector<vector<int>> &rt,queue<TreeNode*> &que) {
        int size = que.size();
        vector<int> cur;
        
        while (size > 0) {
            TreeNode *t = que.front();
            que.pop();
            cur.push_back(t->val);
            if (t->left != NULL) que.push(t->left);
            if (t->right != NULL) que.push(t->right);
            size--;
        }
        
        return cur;
    }


    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> rt;
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        int level = 0;
        
        while (!que.empty()) {
            vector<int> cur = zig(rt,que);
            if (level % 2 == 1) {
                reverse(cur.begin(),cur.end());
            }
            rt.push_back(cur);
            level++;
        }
        
        return rt;
    }
};

Distinct Subsequences
--------------------------------------------------------------
Classic DP
Further reading:
http://stackoverflow.com/questions/20459262/distinct-subsequences-dp-explanation

class Solution {
public:
    int numDistinct(string S, string T) {
        int m = S.length();
        int n = T.length();
        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
        
        for (int i = 0; i < m + 1; i++) {
            dp[i][n] = 1;
        }
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (S[i] == T[j]) {
                    dp[i][j] = dp[i+1][j] + dp[i+1][j+1];
                }else {
                    dp[i][j] = dp[i+1][j];
                }
            }
        }
        return dp[0][0];
    }
};

Update Nov-21-2014
If S[i] != T[j], we know that N[i][j] = N[i+1][j]
If S[i] = T[j], we have a choice. We can either 'match' these characters and go on with the next characters of both S and T, or we can ignore the match (as in the case that S[i] != T[j]).

递归：
COME_BACK
遇到这种题时，找小的test case，为了发现规律：如(ab, b)

int distinct(string s,string t) {
    if (t.length() == 0) return 1;
    if (s.length() == 0) return 0; 
    
    if (s[0] == t[0]) {
        return foo(s.substr(1),t.substr(1)) + foo(s.substr(1),t);
    }
    return foo(s.substr(1),t);
}