235. 二叉搜索树的最近公共祖先 

思路：

1. 按照搜索普通二叉树的最近公共祖先进行搜素，后序遍历，如果==则返回节点

2. 根据二叉搜索树特性进行寻找

边界条件：

if(root==NULL) return root;

分成三种情况：

1. p&&q都在root左边，则数值都比root小。那么当数值都比root小时，继续向左遍历；

2. p&&q都在root右边，则数值都比root大。当数值都比root大时，继续向右遍历；

3. pq一个在左一个在右，说明root就是最近的公共祖先，返回root；

看视频后：

没有中的处理。

迭代法也很简单，因为确定了搜索方向

701.二叉搜索树中的插入操作

思路：

单独建一个函数，返回为void类型：

void Insert(TreeNode *root,TreeNode *newNode)

终止条件：

root==NULL

分情况讨论：

如果newNode数值大于root数值，则应该存放在右边，此时看root->right是否为空，为空则插入节点，不为空则向下寻找。小于则存放左侧，同理。

看视频后：

可以在有返回值的情况下实现。

if (root == NULL) {

    TreeNode* node = new TreeNode(val);

    return node;

}

把node返回给上一层。

450.删除二叉搜索树中的节点（二刷注意）

思路：

分情况讨论：

1.没找到，直接return

2.叶子节点，直接删除

3.有左无右，变成左

4.有右无左，变成右

5.有左有右，？变成右？怎么处理左？

看视频后：

删除需要修改树的结构！

终止节点：

1. 如果root==NULL return NULL

2. key==val的情况下分成四种情况，最后一种有左有右，把cur设置在root->right,找到右子树下最小节点while(cur->left!=NULL) cur=cur->left; cur->left=root->left; 返回root->right, 返回右子树

左遍历：

如果key小于val，向左遍历，返回给root->left;

右遍历：

如果key大于val,向右遍历，返回给root->right;

最后return root;