Binary Tree 2 - Binary Search Tree

TreeNode* closestBST(TreeNode* root, int val){ 
    if(!root) return NULL; 
    if(root->val == val) return root; 
    if(val < root->val){ 
        if(!root->left) return root; 
        TreeNode * p = closestBST(root->left, val); 
        return abs(p->val - val) > abs(root->val - val) ? root : p; 
    }else{ 
        if(!root->right) return root; 
        TreeNode * p = closestBST(root->right, val); 
        return abs(p->val - val) > abs(root->val - val) ? root : p; 
    }    
    return NULL; 
}

void findKnn(TreeNode* node, int k, int target, deque<int>& out){ 
    if (!node) return;
    // 先扫左边的：相当于一个大的滑动窗口，所以用queue实现
    findKnn(node->left, k, target, out);
    if (out.size() < k) 
        out.push_back(node->val); 
    else if(out.size() == k){ 
        if (abs(target-node->val)<abs(target-out.front())){ 
            out.pop_front(); 
            out.push_back(node->val);   //替换出更合适的
        } else
            return;    //这样可以退出了吧，不用继续了！
    } 
    findKnn(node->right, k, target, out);  //再弄右边的
} 

// wrong case: {10,5,15,#,#,6,20}
bool isValidBST(TreeNode *root) {
  if(root == NULL) {
    return true;
  }
  if(root->left && root->left->val >= root->val)
    return false;
  if(root->right && root->right->val <= root->val)
    return false;
  return isValidBST(root->left) && isValidBST(root->right);
}

bool isValidBST(TreeNode *root) {
  // 若测试用例有INT_MIN节点，则此方法不可行！
  return isValidBSTCore(root, INT_MIN, INT_MAX);
}
// 不需要加&，从上往下传
bool isValidBSTCore(TreeNode *root, int minval, int maxval) {
  if(root == NULL)    //注意空的情况
    return true;
  if(root->val <= minval || root->val >= maxval)  //包括 ==
    return false;
  return isValidBSTCore(root->left, minval, root->val) 
        && isValidBSTCore(root->right, root->val, maxval);
}

bool isValidBSTHelper(TreeNode *root, TreeNode * &prev) {  // 注意! TreeNode* &prev
  if(root == NULL) {
    return true;
  }
  if(!isValidBSTHelper(root->left, prev))
    return false;
  if(prev != NULL &&　prev->val >= root->val) {
    return false;
  }
  prev = root;
  return isValidBSTHelper(root->right, prev);
}
bool isValidBST(TreeNode *root) {
  TreeNode *prev = NULL; //!不能直接传入NULL，需要是个左值
  return isValidBSTHelper(root, prev);
}

bool isValidBST(TreeNode * root) {
    stack<TreeNode*> s;
    TreeNode *node = root, *prev = nullptr;
    while(!s.empty() || node) {
        while(node) {
            s.push(node);
            node = node->left;
        }
        node = s.top();
        s.pop();
        // 中序的访问时机
        if(prev != nullptr && prev->val >= node->val)
            return false;
        prev = node;
        node = node->right; //转向右子树
    }
    return true;
}

void recoverTree(TreeNode *root) {
    // O(n)空间，中序遍历，用一个vector保存所有的节点值
    // ==》转化问题为 在数组中找逆序的一对数字
    vector<TreeNode*> index;
    inTraverse(root, index);
    int left=0, right=index.size()-1;
    for(;left < right; left++)  //从前往后，找第一个逆序
        if(index[left]->val > index[left+1]->val)
            break;
    for(;right > left; right--)   //从后往前，找第二个逆序
        if(index[right]->val < index[right-1]->val)
            break;
    swap(index[left]->val, index[right]->val);
}
void inTraverse(TreeNode* node, vector<TreeNode*> &index) {
    if(node == NULL)
        return;
    inTraverse(node->left, index);
    index.push_back(node);
    inTraverse(node->right, index);
}

void recoverTree(TreeNode *root) {
    // O(1)空间的话，就是在中序遍历的时候，直接保存逆序的2个数字
    TreeNode *left=NULL, *right=NULL, *pre=NULL;
    inTraverse(root, pre, left, right); //找到这样的两个点
    swap(left->val, right->val);
}
void inTraverse(TreeNode *node, TreeNode *&pre, TreeNode *&left, TreeNode *&right) { //取地址&才能返回
    if(node == NULL)
        return;
    inTraverse(node->left, pre, left, right);   //就这2行中间有变化
    if(pre != NULL && pre->val > node->val){
        if(left == NULL)
            left = pre;     //left的话，是pre有问题!!
        //right的话，是node，立马赋值为node，但之后很可能会更新，一直真正找到!
        right = node;
    }
    pre = node;
    inTraverse(node->right, pre, left, right);
}

TreeNode *sortedArrayToBST(vector<int> &num) {
    //从中间划分，也是递归的思路
    int size = num.size();
    return sortedArrayToBSTCore(num, 0, size-1);
}
TreeNode *sortedArrayToBSTCore(vector<int> &num, int start, int end) {
    if(start > end)     return NULL;
    int mid = start + ((end-start)>>1);
    TreeNode *node = new TreeNode(num[mid]);
    //if(start == end)    return node;  下边也包括了，不需要单独来
    node->left = sortedArrayToBSTCore(num, start, mid-1);
    node->right = sortedArrayToBSTCore(num, mid+1, end);
    return node;    
}

TreeNode *sortedListToBSTCore(ListNode *head, int size) {  //有几个元素
  if (size <= 0)  //有"="，0代表没有节点，直接返回NULL
    return NULL;
  int mid = size >> 1;
  int step = 0;
  ListNode *pToMid = head;
  while (step++ < mid) {
    pToMid = pToMid->next;  //找到中间的节点
  }
  TreeNode *root = new TreeNode(pToMid->val);   //初始化
  root->left = sortedListToBSTCore(head, mid);  //前一半是 mid 的长度
  // 从pToMid->next开始，注意计算好-1
  root->right = sortedListToBSTCore(pToMid->next, size - mid - 1);
  return root;
}
TreeNode *sortedListToBST(ListNode *head) {
  //首先模拟上题的解法
  if (head == NULL) return NULL;
  ListNode *p = head;
  int size = 1;
  while (p->next != NULL) {
    size++;
    p = p->next;
  }
  return sortedListToBSTCore(head, size);
}

TreeNode *sortedListToBSTCore(ListNode *&root, int size) {  //注意! &
  if (size == 0) return NULL;
  // 注意，这几句的顺序，root被带回新的节点值了!
  TreeNode *leftNode = sortedListToBSTCore(root, size / 2);
  TreeNode *parent = new TreeNode(root->val);
  parent->left = leftNode;
  root = root->next;  // root赋新值
  parent->right = sortedListToBSTCore(root, size - size / 2 - 1);
  return parent;
}
TreeNode *sortedListToBST(ListNode *head) {
  //链表不能随机读取，用上题的解决方案不便捷，考虑从底向上建树timeO(n),spaceO(logn)
  int len = 0;
  ListNode *p = head;
  while (p) {
    len++;
    p = p->next;
  }
  return sortedListToBSTCore(head, len);
}

// 空间O(1) : 用了中序的模板
DoublyListNode *head = NULL;
DoublyListNode *end = NULL;
DoublyListNode *bstToDoublyList(TreeNode *root) {
  if (root == NULL) return NULL;  // 1，返回
  bstToDoublyList(root->left);    // 2，处理左边的
  // 3，中间的步骤
  DoublyListNode *node = new DoublyListNode(root->val);
  node->prev = end;
  if (end == NULL)  //若是开头节点
    end = head = node;
  else
    end->next = node;
  end = node;
  bstToDoublyList(root->right);  //搞右边的
  return head;
}

void readBSTHelper(int min, int max, int &insertVal,
                   BinaryTree *&p, ifstream &fin) {
  if (insertVal > min && insertVal < max) {
    int val = insertVal;
    p = new BinaryTree(val);
    if (fin >> insertVal) {
      // 一直读到10，然后发现40不合适，就一直返回，直到执行到
      readBSTHelper(min, val, insertVal, p->left, fin);
      readBSTHelper(val, max, insertVal, p->right, fin);
    }
  }
}
void readBST(BinaryTree *&root, ifstream &fin) {
  int val;
  fin >> val;
  readBSTHelper(INT_MIN, INT_MAX, val, root, fin);
}

int numTrees(int n) {
    //DP pdf中有透彻分析!! 
    //即，从1到n轮流为根，每种情况的数目=左子树数目*右子树数目(排列组合嘛)
    vector<int> f(n+1, 0); //从0到n 先都初始化为0!
    f[0] = f[1] = 1;    //注意f(0)和f(1)都是1种，空树也是一种!
    for(int i=2; i<=n; i++) {    //从第2个元素开始计算
        for(int j=1; j<=i; j++) //从1到i轮流为根元素  相当于求和一直
            f[i] += f[j-1] * f[i-j];
    }
    return f[n];
}

vector<TreeNode *> generateTrees(int n) {
    return generateTreesCore(1,n);
}
vector<TreeNode *> generateTreesCore(int left, int right) {
    vector<TreeNode *> res;
    if(left > right) {    //递归，收敛条件
        res.push_back(NULL);  //压进去一个NULL的tree
        return res;
    }
    //开始遍历，从left到right，分别当头结点
    for(int i=left; i<=right; i++) {
        vector<TreeNode *> leftTree = generateTreesCore(left, i-1);
        vector<TreeNode *> rightTree = generateTreesCore(i+1, right);
        // 左右子树，排列组合起来构成结果
        for(int j=0; j<leftTree.size(); j++) {
            for(int k=0; k<rightTree.size(); k++){
                TreeNode *head = new TreeNode(i);   //头
                head->left = leftTree[j];
                head->right = rightTree[k];
                res.push_back(head);
            }
        }
    }
    return res;
}

TreeNode* insertNode(TreeNode* root, TreeNode* node) {
  if(root == NULL || node == NULL)
    return node;  // if root is {}, return {node}
  if(root->val < node->val) {
    if(root->right == NULL)
      root->right = node;
    else
      insertNode(root->right, node);
  } else {
    if(root->left == NULL)
      root->left = node;
    else
      insertNode(root->left, node);
  }
  return root;
}

TreeNode* insertNode(TreeNode* root, TreeNode* node) {
  // write your code here
  if(root == NULL || node == NULL)
    return node;
  TreeNode* p = root;
  while(p != NULL) {
    if(p->val < node->val) {
      if(p->right == NULL) {
        p->right = node;
        break;
      }
      p = p->right;
    } else {
      if(p->left == NULL) {
        p->left = node;
        break;
      }
      p = p->left;
    }
  }
  return root;
}

TreeNode* removeNode(TreeNode* root, int value) {
    TreeNode dummyNode(-1);  // in case delete root
    dummyNode.right = root;
    deleteNode(root, value, &dummyNode);  // 传个parent，好操作
    return dummyNode.right;
}
// helper function
void deleteNode(TreeNode* root, int value, TreeNode* parent) {
    if(root == NULL)  return;
    // 先通过递归，找到这个点
    if(root->val < value) {
        deleteNode(root->right, value, root);
        return;
    }
    if(root->val > value) {
        deleteNode(root->left, value, root);
        return;
    }
    // find and delete
    // case 1: leaf node
    if(root->left==NULL && root->right==NULL) {
        if(parent->left == root) {
            parent->left = NULL;
        } else {
            parent->right = NULL;
        }
        delete root;
        return;
    }
    // case 2: only one child
    if(root->left==NULL || root->right==NULL) {
        if(parent->left == root) {
            parent->left = root->left ? root->left : root->right;
        } else {
            parent->right = root->right ? root->right : root->left;
        }
        delete root;
        return;
    }
    // case 3: 2 children
    // step1: find the smallest of the right，后继节点
    TreeNode *minNode = root->right;
    if(minNode->left == nullptr) {  // 如果右儿子没有左子树，那后继节点就是右儿子
        root->val = minNode->val;
        root->right = minNode->right;
        return;
    }
    while(minNode->left != NULL) {
        parent = minNode;  // parent不需要了，可以用一用
        minNode = minNode->left;
    }
    // step 2: copy the val
    root->val = minNode->val;
    // step 3: delete it
    parent->left = nullptr;
    delete minNode;
}

// helper function
void deleteNode(TreeNode* root, int value, TreeNode* parent) {
    if(root == NULL)  return;
    if(root->val < value) {
        deleteNode(root->right, value, root);
        return;
    }
    if(root->val > value) {
        deleteNode(root->left, value, root);
        return;
    }
    // find and delete
    // case 1: leaf node and case 2: only one child
    if(root->left==NULL || root->right==NULL) {
        if(parent->left == root) {
            parent->left = root->left ? root->left : root->right;
        } else {
            parent->right = root->right ? root->right : root->left;
        }
        delete root;
        return;
    }
    // case 3: 2 children
    // step1: find the smallest of the right，后继节点
    TreeNode *minNode = root->right;
    if(minNode->left == nullptr) {  // 如果右儿子没有左子树，那后继节点就是右儿子
        root->val = minNode->val;
        root->right = minNode->right;
        return;
    }
    while(minNode->left != NULL) {
        parent = minNode;  // parent不需要了，可以用一用
        minNode = minNode->left;
    }
    // step 2: copy the val
    root->val = minNode->val;
    // step 3: delete it
    parent->left = nullptr;
    delete minNode;
}

vector<int> searchRange(TreeNode* root, int k1, int k2) {
  vector<int> res;
  DFS(res, root, k1, k2);
  return res;
}
void DFS(vector<int> &res, TreeNode* root, int k1, int k2) {
  if(root == NULL)  return;
  /*if(root->val > k2 || root->val < k1) {
        return;  // 错误剪枝,return早了，子树可能有在范围里的
  }*/
  if(root->val >= k1) { //优化，如果超出范围，剪枝！
    DFS(res, root->left, k1, k2);
  }
  if(root->val >= k1 && root->val <= k2) {
    res.push_back(root->val);
  }
  if(root->val <= k2) {
    DFS(res, root->right, k1, k2);
  }
}

vector<int> searchRange(TreeNode * root, int k1, int k2) {
    vector<int> res;
    if(root == nullptr) return res;
    if(root->val < k1) return searchRange(root->right, k1, k2);
    if(root->val > k2) return searchRange(root->left, k1, k2);
    res = searchRange(root->left, k1, k2);
    res.push_back(root->val);
    vector<int> right = searchRange(root->right, k1, k2);
    res.insert(res.end(), right.begin(), right.end());
    return res;
}

/**
 * Example of iterate a tree:
 * BSTIterator iterator = BSTIterator(root);
 * while (iterator.hasNext()) {
 *    TreeNode * node = iterator.next();
 *    do something for node
 */
class BSTIterator {
public:
    stack<TreeNode*> s;
    TreeNode *cur;
    //@param root: The root of binary tree.
    BSTIterator(TreeNode *root): cur(root) {}
    //@return: True if there has next node, or false
    bool hasNext() {
        return (cur != nullptr) || (!s.empty());
    }
    //@return: return next node
    TreeNode* next() {
        // find cur->next before return cur
        while(cur != nullptr) { //go to left-most
            s.push(cur);
            cur = cur->left;
        }
        TreeNode* nxt = s.top();
        s.pop();
        cur = nxt->right;
        return nxt;
    }
};

// 错误解法：2,1这种树，1的后继为2，是它的父节点，所以递归写法拿不到父节点，不可行
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
  if(root == NULL)  return NULL;
  if(p == root) {
    TreeNode* successor = root->right;
    while(successor->left != NULL) {
      successor = successor->left;
    }
    return successor;
  }
  if(p->val > root->val) {
    return inorderSuccessor(root->right, p);
  } else {
    return inorderSuccessor(root->left, p);
  }
}
/*
本题是要确定中序遍历的后继:
如果该节点有右子节点, 那么后继是其右子节点的子树中最左端的节点；
如果该节点没有右子节点, 那么后继是它的某个祖先(不是左祖先，是右边祖先), 该节点在这个祖先的左子树内.
使用循环实现:
查找该节点, 并在该过程中维护上述性质的祖先节点
查找到后, 如果该节点有右子节点, 则后继在其右子树内; 否则后继就是维护的那个祖先节点
*/
TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
  if(root == NULL)  return NULL;
  TreeNode* successor = NULL;  // 题目要求了，如果没有就返回nullptr
  // find p
  while(root != p) {
    //successor = root;  // 记录上一个后继:不是这里记！
    if(p->val > root->val) {
      root = root->right;
    } else {
      successor = root;  // 记录上一个后继:这里记！往左走的时候
      root = root->left;
    }
  }
  // if no right child, then return parent
  if(p->right == NULL) {
    return successor;
  }
  // has right child, then find the leftmost child
  successor = root->right;
  while(successor->left != NULL) {
    successor = successor->left;
  }
  return successor;
}
/*
使用递归实现:
如果根节点小于或等于要查找的节点, 直接进入右子树递归
如果根节点大于要查找的节点, 则暂存左子树递归查找的结果, 如果是 null, 则直接返回当前根节点; 反之返回左子树递归查找的结果.
在递归实现中, 暂存左子树递归查找的结果就相当于循环实现中维护的祖先节点.
很难理解，推荐非递归实现
*/
TreeNode * inorderSuccessor(TreeNode * root, TreeNode * p) {
    if(root == nullptr || p == nullptr) return nullptr;
    if(p->val >= root->val) {
        return inorderSuccessor(root->right, p);
    } else {
        TreeNode * left = inorderSuccessor(root->left, p);
        return left ? left : root;
    }
}