questions other than leetcode

Q1: check if a tree is a complete binary tree
利用 BFS breadth first search， 标记第一个lack of child 的node, 如果已经发现了一个lack of child的node, 那么在这个node之后是不能再lack of child的。逻辑还是很清晰的·。
这里是不能利用DFS来遍历tree的，因为DFS遍历node的顺序不能帮助我们解决这个问题。
complete binary tree用BFS遍历之后可以获得一个array， 这个array就能代表一些问题。

class Solution {
 public:
  bool isCompleted(TreeNode* root) {
    //sanity check
    if (root == NULL) return true;
    queue<TreeNode*> explore;
    bool flag = false;//mark the first node lack of child
    explore.push(root);
    while(!explore.empty()) {
      TreeNode* tmp = explore.front();
      explore.pop();
      //check if the node lack of child
      if (flag == true) {//one  node is lack of child
        if (tmp->left == NULL && tmp->right == NULL) {}
        else return false;//if the flag is true, there should be no any child nodes afterwards
      }else {//no node lack of child until now
        if (tmp->left == NULL && tmp->right != NULL) return false; // the node has no left child node but has right child node
        if (tmp->left == NULL || tmp->right == NULL) flag = true; //the node lack of at least one child node
        if (tmp->left != NULL) explore.push(tmp->left);
        if (tmp->right != NULL) explore.push(tmp->right);
      }
    }
    //if has traversed all of the nodes and not return false, then it's a complete binary tree
    return true;
  }
};

Q2：heap sort

Q3: 倒序遍历perfect tree

Q4: 2 sum in binary search tree
这个题目有很多种方法：
M1： 比较投机取巧： 利用一个array, inorder 遍历这个BST， 把结果存到array里面，然后do 2 sum over the array， time complexity: O (n), space complexity: O(n)
M2 :   inplace + O(n) time complexity, but change the original tree structure. use recursion to change the binary search tree into double linked list using inorder traversal. then do 2 sum over the double linked list
M3:  space complexity: O(logn) + time complexity: O(n), use 2 stack to do inorder traversal over left subtree and right subtree in iterative way, from bottom to top, find the next largest node or find the next smallest node and do two sum. 利用两个阀门， 一个控制左子树的遍历（from smallest to largest），一个控制右子树的遍历(from largest to smallest)，双向inorder traversal, 找到相对应的值之后看是否为sum。
M3 的实现代码：tree的 preorder traversal 和 inorder traversal的iterative 的写法非常重要

bool 2sumBST(TreeNode* root) {

stack<TreeNode*> lstack;
stack<TreeNode*> rstack;

bool openl = false;
bool openr = false;

TreeNode* cur1 = root;
TreeNode* cur2 = root;

int val1 = 0;
int val2 = 0;
while (true) {

while (openl == false) {
if (cur1 != NULL) {
lstack.push(cur1;
cur1 = cur1->left;
} else {
if (lstack.empty()) {
openl = true;
} else {
TreeNode* tmp = lstack.pop();
val1 = tmp->val;
cur1 = tmp->right;
openl = true;
}
}
}

while (openr ==  false) {
if (cur2 != NULL) {
rstack.push(cur);
cur2 = cur2->right;
} else {
if (rstack.empty()) {
openr = true;
} else {
TreeNode* tmp = rstack.pop();
val2 = tmp->val;
cur2 = tmp->left;
openr = true;
}
}

}

//check 2 sum
if (val1 != val2 && val1 + val2 == target) {
return true;
} else  if (val1 + val2 < target) {
openl = false; //go the left subtree
} else if (val1 + val2 > target) {
openr = false;  //go the right subtree
} else if (val1 >= val2) {
return false;
}
}

}
时间复杂度： O(n) bloomberg onsite 原题！

Q4: BST， 给定一个区间，删除所有区间 之外的node, 返回modify 这个树的root
How to do a  BST related problems.
需要在BST里面找出所有在区间之外的node， 并删除（delete nodes in BST）, BST的题目要充分利用BST的性质，分析每个node的可能情况，对于不同的情况，怎么去处理这个node, 思维逻辑要清晰。  比如这个题目：一个node可能有两种情况:
case1: the node value is in the interval, we do nothing
case2: the node is not in the interval, if the node is smaller than min, then the left subtree of the node can be all deleted; if the node is larger than max, then the right subtree of the node can be all deleted
we can bottom-up recursion to solve this problem.
TreeNode* remove(TreeNode* root, int min, int max) {
         if (root == NULL) return NULL;
         //bottom-up recursion
        //get modified left subtree and modified right subtree
        root->left = remove(root->left, min, max);
        root->right = remove(root->right, min, max);
        // Current node do what in current level
       // case2：delete all the left subtree
       if (root->val < min)   {
              TreeNode* tmp = root->right;
               delete root;
              return tmp;
      }
      //case3: delete all the right subtree
     if (root->val > max) {
             TreeNode* tmp = root->left;
             delete root;
             return tmp;
    }
    return root;
}


Q5： 垂直遍历
这个题目主要是需要知道在同一个vertical 线上node有哪些，我们需要知道每个Node 距离原点horizontal的距离，这个可以通过go left -1, go right +1来获得，将同一个vertical上的nodes存在一个map里面，最后输出即可。