二叉搜索树的最近公共祖先
题目
根据二叉搜索树的特性，它的公共祖先肯定是值夹在p和q之间的（满足此条件的第一个点）
TreeNode* getroot(TreeNode* root,TreeNode* p,TreeNode* q){
if(rooot==NULL) return NULL;
if(root->val<p->val&&root->val<q->val){
return getroot(root->right,p,q);
}
else if(root->val>p->val&&root->val>q->val)
return getroot(root->left,p,q);
else
return root;
}
二叉搜索树中的插入操作
题目
其实就是想二分查找插入数组时一样，一直到空节点，然后创建空间。
TreeNode* fun.....
if(cur==NULL){
cur=new TreeNode(val);
return cur;
}
if(cur->val<val){
cur->right=fun(cur->right);//用来接住结果
}
...
或者一开始直接在参数那加个引用，这样就可以直接更改right和left
TreeNode* fun（TreeNode* &cur）…
删除二叉搜索树中的节点。
题目
首先应该先找到要删除的节点，然后分情况讨论。
1.要删除的是叶子节点。
2.要删除的节点有一边为空。
3.要删除的节点两边都不为空
如果删除的节点两边都不为空，那左边会比右边所有都小，右边会比左边所有都大，所以有两种接发：1.找到右子树的最左边，把左子树接到那里。2.找到左子树的最右边，把右子树接到那里。
要得到删除后的根节点，所以函数返回TreeNode*
TreeNode* delete(TreeNode*cur,int key){
if(cur==NULL) return NULL;//找遍了也没找到
if(cur->val==key){
if(cur->left==NULL&&cur->right==NULL)
return NULL;
else if(cur->left!=NULL&&cur->right==NULL)
return cur->left;//将它返回给cur的上一层
else if(cur->right!=NULL&&cur->left==NULL)
return cur->right;
else{
TreeNode* temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
TreeNode* a=cur->right;
delete cur;
return a;
}
}
if(cur->val<key)
cur->right=delete(right,key);//cur->right接住更改后的结果
if(cur->val>key)
cur->left=delete(left,key);
return root;
}