前言
今日文案：
与其埋怨世界，不如改变自己。管好自己的心，做好自己的事，比什么都强。人生无完美，曲折亦风景。别把失去看得过重，放弃是另一种拥有；不要经常艳羡他人，人做到了，心悟到了，相信属于你的风景就在下一个拐弯处。
一、二叉搜索树最近的公共祖先
在前面做过 二叉树最近的公共祖先，二叉搜索树作为一种特殊情况，一样适用，我们只要用后序遍历，向上传递消息，看是否有节点就行，这里我们用另外一种利用搜索树特性的方法。
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==NULL) //空直接反空 { return root; } if(p->val<root->val&&q->val<root->val) //判断p q大小，往左去遍历 { TreeNode*left=lowestCommonAncestor(root->left,p,q); //左 if(left!=NULL) { return left; } } else if(p->val>root->val&&q->val>root->val) //右 { TreeNode*right=lowestCommonAncestor(root->right,p,q); if(right!=NULL) { return right; } } return root; }
在这个过程中，我们没有判断p->valval>root 或者q->valval>root，也就是两个点在根节点两边，这种情况。其实想想可以知道，这种情况一旦出现，root就已经是我们要找的最近公共祖先，可以直接返回。
而我们的遍历就一直在等待这种情况出现，一旦出现就马上一层一层返回。
二、二叉搜索树中的插入操作
解题思路：
插入，就像链表一样，只要创建一个节点吗，然后改变父节点的指向，和新节点的指向就行，这里的关键是找到插入那里，这就是搜索树的特性了。插入的位子都是作为叶子。
class Solution { public: TreeNode* traversal(TreeNode* cur, int val) { if(cur==0) //创建节点 { TreeNode*node=new TreeNode(val); return node; } if(val>cur->val) //寻找插入位置 { cur->right=traversal(cur->right,val); } else { cur->left= traversal(cur->left,val); } return cur; } TreeNode* insertIntoBST(TreeNode* root, int val) { return traversal(root,val); } };
三、删除二叉搜索树中的节点
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root==0) { return NULL; } if(root->val==key) { if(root->left==NULL&&root->right==NULL) //搜到叶子节点了，没搜到就返回 { return NULL; } if(root->left==NULL&&root->right!=NULL) //判断单孩子，左or右 { return root->right; //返回上一层链接它 } if(root->left!=NULL&&root->right==NULL) { return root->left; } else //这是两边都有的，那就爆掉 { TreeNode*node=root; node=node->right; //左孩子全部插入右孩子的左子树末端 while(node->left) //搜索树大小排列特性 { node=node->left; } node->left=root->left; return root->right; } } if(key>root->val) //搜索方向 { root->right=deleteNode(root->right,key); } if(key<root->val) { root->left=deleteNode(root->left,key); } return root; } };
因为右子树一定>中节点（被删除的节点）>左子树，那中节点被删后，左子树的值肯定是大于中节点（被删除节点）的父节点，它又小于右子树的所有点，它只能插入在右子树最小的点的后面，也就是右子树，左下角叶子节点后面。
总结
搜索树关键终于判断方向，删除搜索树节点，关键要分清楚不同的情况，还有搜索树特性：左子树都比根节点小，右子树都比根节点大。
