Day 65 - 2, #95, #99, Unique Binary Search Trees II, Recover Binary Search Tree

Unique Binary Search Trees II
Given 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

-----------------------------------------------------------------------------------------
COME_BACK, Catalan number
Similar to #96 Unique Binary Search Trees
resource: http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf
there is space for optimization

/**
 * 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<TreeNode *> helper(int start, int end) {
        vector<TreeNode*> rt;
        for (int i = start; i <= end; i++) {
            vector<TreeNode*> left = helper(start,i - 1);
            vector<TreeNode *> right = helper(i + 1, end);
            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode *root = new TreeNode(i + 1);
                    root->left = left[j];
                    root->right = right[k];
                    rt.push_back(root);
                }
            }
        }
        if (rt.size() == 0) rt.push_back(NULL);
        return rt;
    }

    vector<TreeNode*> generateTrees(int n) {
        return helper(0,n - 1);
    }
};

iterative,
OJ的要求的root左边的value一定比它小，右边一定被它大，因为是BST

/**
 * 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:
    TreeNode *deepCopy(TreeNode *root,int offset) {
        if (root == NULL) return NULL;
        TreeNode *newRoot = new TreeNode(root->val + offset);
        newRoot->left = deepCopy(root->left,offset);
        newRoot->right = deepCopy(root->right,offset);
        return newRoot;
    }

    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> rt;
        vector<vector<TreeNode *>> dp(n + 1,vector<TreeNode*>());
        dp[0].push_back(NULL);
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                for (int left = 0; left < dp[j].size(); left++) {
                    for (int right = 0; right < dp[i - j - 1].size(); right++) {
                        TreeNode *root = new TreeNode(j + 1);
                        root->left = deepCopy(dp[j][left],0);
                        //root->left = dp[j][left];
                        root->right = deepCopy(dp[i - j - 1][right],j + 1);
                        dp[i].push_back(root);
                    }
                }
            }
        }
        
        return dp[n];
    }
};

O(1)额外空间
https://leetcode.com/discuss/20399/share-a-c-dp-solution-with-o-1-space
Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
-------------------------------------------------------
Solution #1: O(n) space - construct an array of size n, populate it by traversing tree in in-order...

Solution #2: in-space and iterative. Morris traversal:
http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/ 

Solution #3: In-space - typical in-order traversal , reach to the left most node, then walk back to the right most.
pre points to the node right before the current node in serialized binary tree.
The following code implements #3.

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode *pre;
    TreeNode* first;
    TreeNode* second;

    void inorder (TreeNode *root) {
        if (root == NULL) {
            return;
        }
        
        inorder(root->left);
        if (pre == NULL) {
            pre = root;
        }
        
        // found it!
        if (pre->val > root->val) {
            if (first == NULL) {
                first = pre;
            }
            second = root;
        }
        
        pre = root;
        inorder(root->right);
    }

    void recoverTree(TreeNode *root) {
        pre = NULL;
        first = NULL;
        inorder(root);
        int temp = first->val;
        first->val = second->val;
        second->val = temp;
    }
};

Update Nov-19-2014 
watch out for pointer passing  as argument in C++