Leetcode second round: 8/26

today's mission: 109-94

94: binary tree inorder traversal

这个题目很重要，在之前也总结过， inorder traversal iteration的方法关键在于需要一个cur指针还表明左子树是否已经遍历完，可以开始遍历右子树了。注意循环的条件是!stack.empty() || cur != NULL分别表示stack里面没有元素， 并且左子树已经遍历完了。

95/96：unique binary search tree I II
I 通过列举可以直到属于一维动态规划的问题， 从子问题到最终问题的求解。
II 这个题目跟之前在一个数学计算式里面加括号能得到几种结果的思想一样，都是用的分而治之的方法， 即对于每一个可能的root node, 找到所有的左子树，找到所有的右子树， 然后把这些左右子树分别进行组合， 就可以得到最后的结果了。
分而治之的思想和DFS找所有可能解类似，能够找到所有可能解。

97： interleaving string
这个属于3个string的2D DP的问题，感觉这个Interleaving string 这种题目经常考，交错插入字母，在这个题目中，二维DP的元素含义是：M[s1.size()+1][s2.size()+1];//M[i][j]: 0-i: s1, 0-j: s2, s3:0-i+j is interleaving string of s1, s2， 确定含义之后就是找induction rule了， 对于二维dp,可以观察， M[i][j] 和M[i-1][j], M[i][j-1], M[i-1][j-1]的关系， 能否由这三者之间的一个， 两个，或者三个量来确定。然后我们可以画二维表格来证实我们的想法是正确的。 最后还需要确定base case, 即在问题的解是在小空间内的结果。
        //base case
        M[0][0] = true;
        for (int i = 1; i <= s1.size(); i++) {
            if (s1.substr(0,i) == s3.substr(0,i)) M[i][0] = true;
            else M[i][0] = false;
        }
        for (int i = 1; i <= s2.size(); i++) {
            if (s2.substr(0,i) == s3.substr(0,i)) M[0][i] = true;
            else M[0][i] = false;
        }
induction rule :
if (M[i-1][j] && s1[i-1] == s3[i+j-1]) || (M[i][j-1] && s2[j-1] == s3[i+j-1])) M[i][j] = true;

98: validate binary search tree
BST要结合BST的性质， 每个节点左边小于root,右边大于root, 所以传入每个node的时候要传入这个Node的左右两个边界
特别要注意的是： 对于边界root->val == INT_MAX的判断，如果出现这种情况，我们需要把min, max边界的值设置为 LONG_MIN, LONG_MAX，并且相应的类型应该设置为long

99: recover binary search tree

100: same tree
101:synmetric tree
这两个题目用的树的递归算法是相似的，属于basic tree traversal(preorder) + 条件判断, 自顶向下地判断。
102: binary tree level order traversal
107: binary tree level order traversalII
103: binary tree zigzag level order traversal
这两个题目都是考察BT level order traversal, 第一个基本的level order traversal很容易实现，也是很基础的东西，第二个就是第一个的结果进行reverse，关键在于第三zigzag level order traversal的话，由于用到了deque，所以在对deque进行操作的时候要小心。pop_back的时候只能push_front， pop_front的时候只能push_back。 先把这些配对写好然后再去判断各属于奇数层还是偶数层。

104：maximum depth of binary tree
这个题目tree bottom-up recursion做也很简单
105：construct binary tree from inorder and preorder traversal
106：construct binary tree from inorder and post order traversal
108：convert sorted array to binary search tree
109：convert sorted list to binary search tree
这四个问题是类似的问题， 属于reconstruct tree的问题，我们只要清楚对于一个root而言，它的左子树的范围， 以及右子树的范围，这是最基础的reconstruct tree的思想。
Note: 这类的问题还有reconstruct binary search tree with preorder, inorder, postorder, level order,处理方式类似，但是具体的规律不同。
时间复杂度：O（n）空间复杂度 O(logn)

109这个题目需要注意：是按照sortedlist的顺序来进行reconstruct的。

class Solution {
private:
    TreeNode* helper(ListNode* &head, int left, int right) {
        TreeNode* rst = NULL;
        if (left > right) {
            return NULL;
        }
        int mid = left + (right-left)/2;
        TreeNode* leftt = helper(head, left, mid-1);
        rst = new TreeNode(head->val);
        head = head->next;
        TreeNode* rightt = helper(head, mid+1, right);
        rst->left = leftt;
        rst->right = rightt;
    }
public:
    TreeNode* sortedListToBST(ListNode* head) {
        if (head == NULL) return NULL;
        int count = 0;
        ListNode* cur = head;
        while (cur) {
            count++;
            cur = cur->next;
        }
        return helper(head, 0, count-1);
    }
};