Reconstruct Binary Tree

reconstruct binary tree 类型的题目general 的思路：
利用递归的思想，在每次确定root之后，分别找出该root对应的left subtree 和right subtree的序列，可以用两个vector分别保存这两个序列，也可以利用在原来序列的边界index来表示着两个序列。


Q1: Reconstruct Binary Tree With Preorder And Inorder

preorder traversal = {5, 3, 1, 4, 8, 11}
inorder traversal = {1, 3, 4, 5, 8, 11}
the corresponding binary tree is
        5
      /    \
    3        8
  /   \        \
1      4        11

analysis:

Preorder traversal of a tree: root-> left-subtree -> right-subtree
Inorder traversal of a tree: left-subtree -> root -> right-subtree
From preorder traversal, we can get the root of the tree. With the root of the tree, in inorder traversal, we can get the left subtree and right subtree. If we know the number of left subtree, we can get the preorder tranversal of left subtree preorder traversal vector; the same as the right subtree.
To find the root index in inorder traversal quickly, we can use a hashmap to store the element and its index in inorder traversal. 
Recursion can be used in this problem

Solution:

//class TreeNode {
// public:
//  int value;
//  TreeNode* left;
//  TreeNode* right;
//  TreeNode(int v) : value(v), left(NULL), right(NULL) {}
//};

class Solution {
 private:
  void helper(TreeNode* &root, vector<int> in, vector<int> pre, int ileft, int iright, int pleft, int pright, map<int, int> inmap) {

    //base case
    //to check if it needs to return if ileft == iright, we can just use a simple   case when  there is only one node in the tree, ileft == iright, can't return NULL;
    if (ileft > iright || pleft > pright) return;
    //recursion rule
    //step1: find root index in inorder
    root = new TreeNode(pre[pleft]);
    int rootI = pre[pleft];
    int rin = inmap[rootI];
    //step2: construct left subtree
    int left_size = rin - ileft;
   // int right_size = iright - rin;
     helper(root->left, in, pre, ileft, ileft+left_size-1, pleft+1, pleft+left_size, inmap);
    //step3: construct right subtree
     helper(root->right, in, pre, rin+1, iright, pleft+left_size+1, pright, inmap);
  }
 public:
  TreeNode* reconstruct(vector<int> in, vector<int> pre) {
    TreeNode* root = NULL;
    //sanitary check
    if (in.size() == 0 || pre.size() == 0) return root;
    //use hashmap to store the element and its index in inorder tranversal
    map<int, int> inmap;//key: element value: index
    for (int i = 0; i < in.size(); i++) {
      inmap[in[i]] = i;
    }
    helper(root, in, pre, 0, in.size()-1, 0, pre.size()-1, inmap);
    return root;
  }
};

Time complexity: traverse the inorder and preorder vector once
 O(n)
Space complexity: O(n) -> construct the tree


Q2: Reconstruct Binary Tree With Postorder And Inorder

postorder traversal = {1, 4, 3, 11, 8, 5}
inorder traversal = {1, 3, 4, 5, 8, 11}
the corresponding binary tree is
        5
      /    \
    3        8
  /   \        \
1      4        11

analysis:
postorder traversal: left-subtree -> right-subtree->root
inorder traversal: left-subtree-> root -> right-subtree
From postorder traversal, we can get the root from the last element in the vector, with the root we can get the left-subtree and right-subtree from the inorder traversal, same as previous question.

Solution:

class Solution {
 private:
  void helper(TreeNode* &root, vector<int> in, vector<int> post, int ileft, int iright, int pleft, int pright, map<int, int> inmap) {
    //base case
    if (ileft > iright || pleft > pright) return;
    //get root index in in
    int rooti = post[pright];
    root = new TreeNode(rooti);
    int rI = inmap[rooti];
    int left_size = rI-ileft;
    helper(root->left, in, post, ileft, ileft+left_size-1, pleft, pleft+ left_size-1, inmap);
    helper(root->right, in, post, rI+1, iright, pleft+left_size, pright-1, inmap);
  }
 public:
  TreeNode* reconstruct(vector<int> in, vector<int> post) {
    //sanitary check
    if (in.size() == 0 || post.size() == 0) return NULL;
    TreeNode* root;
    map<int, int> inmap;
    for (int i = 0; i < in.size(); i++) {
      inmap[in[i]] = i;
    }
    helper(root, in, post, 0, in.size()-1, 0, post.size()-1, inmap);
    return root;
  }
};
Time complexity: O(n);
Space complexity: O(n);

Maximum points in 2D space

Q1: Largest Set Of Points With Positive Slope
Given an array of 2D coordinates of points (all the coordinates are integers), find the largest number of points that can form a set such that any pair of points in the set can form a line with positive slope. Return the size of such a maximal set.

Analysis:
If two pair of points can form a line with positive slop, then (y2-y1)/(x2-x1) > 0. That means if y2 > y1, then x2 > x1; if y2 < y1, then x2 < x1. If all x coordinates are in  ascending order, all y coordinates in solution points should also in ascending order. To solve this problem, we can first sort the points in the order of ascending x, then find the max ascending subsequence of y, that is the result. As the result has to be larger than 2, if the max ascending subsequence is 1, then no pair of points can form a line with positive slop.


Solution:

class cmp {
  public:
  bool operator()(pair<int, int> left, pair<int, int> right) {
    return left.first < right.first;
  }
};
class Solution {
 public:
 //step1: sort the points in the ascending order of x
 //step2: find the maximum ascending subsequence of y
  int largest(vector<pair<int, int> > points) {
    // write your solution here.
    //sanitary check
    if (points.size() == 0) return 0;
    cmp compare;
   
    sort(points.begin(), points.end(), compare);   
    //M[i] represent the max ascendig subsequence of y from 0-i including i
    int *M = new int[points.size()];
    //base case:
    M[0] = 1;
    int global_max = 0;
    for (int i = 1; i < points.size(); i++) {
      int tmp_max = 0;
      for (int j = i-1; j >= 0; j--) {
        if (points[i].second > points[j].second) {
          tmp_max = max(tmp_max, M[j]);
        }
      }
      if (tmp_max > 0) M[i] = tmp_max + 1;
      else M[i] = 1;
      global_max = max(global_max, M[i]);
    }
    if (global_max == 1) return 0; //the result should be larger than 1
    return global_max;
  }
};

Time complexity:
     sort points: O(n logn)
     find max subsequnce : O(n^2)
     Total time complexity : O(n^2)
Space complexity: O(1)