Tips: 忙着改毕业论文，忙着完成导师布置的任务，只能自己偷偷的在晚上的时候刷题- - 最近主要做了一下二叉顺序树的相关题目，题目总体难度一般。
LintCode 661 Convert BST to Greater Tree 虽然是Easy难度的题，但还是很有新意的:D，稍微思考了一下，树相关的题目一定是和递归紧紧联系在一起的，所以这道题就是从最右的叶子节点开始遍历，按照右子树、根节点、左子树这样的方式遍历，同时开了一个sum变量，统计遍历到某个节点时的值。
int sum = 0; TreeNode* convertBST(TreeNode* root) { // Write your code here if (NULL == root) return NULL; root->right = convertBST(root->right); root->val += sum; sum = root->val; root->left = convertBST(root->left); return root; }LintCode 85 Insert Node in a Binary Search Tree 往二元顺序树里插入一个值为val的节点。递归的方式就不说了，这里Challenge里提到能否以非递归的形式实现呢？奈何愚笨，想了半天都没做对。问题主要是出在 最后要返回这个二叉树的根节点。 先看我的错误版本:思路是这样的，首先把最初的root存起来，然后循环去寻找该插入的点，直到root == NULL。然后在该地方新建一个节点，最后返回初始的根节点。看起来美滋滋，可惜错啦！
TreeNode* insertNode(TreeNode* root, TreeNode* node) { // write your code here TreeNode *tmp = root; while (root){ if (node->val < root->val) root = root->left; else root = root->right; } root = new TreeNode(node->val); return tmp; }这种方法的问题就在于没有无法保存连接关系。比如往节点A的左子树插入一节点，如果A节点的左子树为空，A = A->left,然后在 new TreeNode()在此新建一个节点，是无法让 A->left == this new TreeNode。而解决这一问题的办法就是用A->left = new TreeNode()来代替。这样就可以保证连接关系。
TreeNode* insertNode(TreeNode* root, TreeNode* node) { // write your code here if (NULL == node) return root; TreeNode *ret = new TreeNode(node->val); if (NULL == root) return ret; TreeNode *tmp = root; while (tmp){ if (node->val < tmp->val){ if (NULL == tmp->left){ tmp->left = node; return root; } tmp = tmp->left; }else{ if (NULL == tmp->right){ tmp->right = ret; return root; } tmp = tmp->right; } } }LintCode 11 Search Range in Binary Search Tree 返回二叉树内节点值在k1到k2之间的所有值。二叉顺序树内的一个重要的性质就是 中序遍历是 递增序列。题目要求要返回满足要求的递增序列，所以只需要中序遍历一次二元查找树即可。当然还可以加一些遍历条件，让其减少递归的次数。
vector<int> ans; void dfs(TreeNode *root, int k1, int k2) { if (NULL == root) return; dfs(root->left, k1, k2); if (root->val >= k1 && root->val <= k2) ans.push_back(root->val); dfs(root->right, k1, k2); } vector<int> searchRange(TreeNode* root, int k1, int k2) { // write your code here ans.clear(); dfs(root, k1, k2); //sort(ans.begin(), ans.end()); return ans; }LintCode 95 Validate Binary Search Tree 判断一棵给定的二叉树是不是二元查找树。利用性质：二元查找树的中序遍历是递增数列（充要条件）。中序遍历一次给定树，然后判断该vector的后一个元素是不是永远>前一个元素。这里说一个细节:顺序容器的size函数返回的是一个unsigned int,即如果遍历该vector时写成这样for (int i = 0; i < v.size()-1; i++)是有问题的，即当v.size()==0时，系统计算v.size()-1 = -1 => 由于unsigned int 是非负的，所以会把-1转成max(long long)好像是42亿多。。所以推荐写成for (int i =1; i < v.size(); i++)这样的形式。
vector<int> ans; void inorder(TreeNode *root) { if (NULL == root) return; inorder(root->left); ans.push_back(root->val); inorder(root->right); } bool isValidBST(TreeNode *root) { // write your code here //二元查找树的中序遍历是一个递增数列 ans.clear(); inorder(root); for (int i = 1; i < ans.size(); i++){ if (ans[i] <= ans[i-1]) return false; } return true; }LintCode 86 Binary Search Tree Iteration Challenge:Extra memory usage O(h), h is the height of the tree. Super Star: Extra memory usage O(1). 正常思路：用一个vector和一个int指针分别来存储中序遍历的值和当前所指的值。但是这种方法的空间复杂度为O(n)，n是节点个数。题目要求是O(h),也就是O(logn)，所以这个肯定是不对的。 后来上网搜了一下，发现要用堆栈可以满足O(logn)，也是是考察非递归形式的中序遍历。这种迭代的写法很多面试会考到，是bugfree.
stack<TreeNode*> s; BSTIterator(TreeNode *root) { // write your code here while (root){ s.push(root); root = root->left; } } //@return: True if there has next node, or false bool hasNext() { // write your code here return s.size() > 0; } //@return: return next node TreeNode* next() { // write your code here TreeNode *tmp = s.top(); s.pop(); TreeNode* res = tmp; tmp = tmp->right; while (tmp){ s.push(tmp); tmp = tmp->left; } return res; }LintCode 87 Remove Node in Binary Tree 删除二叉查找树中的某一个值为val的节点，先递归的find，然后找到之后删除。删除主要要考虑这么几种情况： 1.如果要删除的节点是叶子节点，那么直接删除。 2.如果是有单个孩子的节点，那么把他的孩子节点放到该位置上即可。 3.如果是双孩子节点，那么需要把 他左孩子的最大节点或者是右孩子的最小节点 放到该位置上，然后删掉那么 左孩子的最大节点或者最大节点(因为这些节点肯定是 孩子节点或者单孩子节点)。
int findMaxInLeft(TreeNode* root){ if (!root->right) return root->val; else return findMaxInLeft(root->right); } TreeNode* removeNode(TreeNode* root, int value) { // write your code here if (NULL == root) return NULL; if (value > root->val){ root->right = removeNode(root->right, value); }else if (value < root->val){ root->left = removeNode(root->left, value); }else{ //find the node needed to be removed. if (!root->left && !root->right){ //leaf node //free(root);// or root = NULL; root = NULL; }else if (root->left && !root->right){ TreeNode *q = root; root = root->left; free(q); }else if (!root->left && root->right){ TreeNode *q = root; root = root->right; free(q); }else{ int val = findMaxInLeft(root->left); root = removeNode(root, val); root->val = val; } } return root; }总结：重点掌握 二元查找树的非递归插值方法、非递归的三种遍历方法。当然二元查找树是很简单的一部分，由此扩展，至少要掌握 avl树的插入节点与删除操作，以及常见的B-tree,B+tree,R-tree的基本概念和应用。
