---

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

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

思路

不同于236普通二叉树，由于是二叉搜索树，只需要第一个遍历到小于q大于p的节点即可。使用只需要遍历一条边的递归方法，设置返回值，将递归函数return。
时间复杂度On

代码

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {if root.Val>q.Val&&root.Val>p.Val{return lowestCommonAncestor(root.Left, p, q)}if root.Val<p.Val&&root.Val<q.Val{return lowestCommonAncestor(root.Right, p, q)}return root
}

困难

二叉搜索树特性。
只遍历一条边。

---

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

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

思路

由于怎么插入都可以，不考虑改变二叉树结构的插入方法，直接插入空节点。

代码

func insertIntoBST(root *TreeNode, val int) *TreeNode {if root==nil{root=&TreeNode{}root.Val = valreturn root}if root.Val<val{root.Right=insertIntoBST(root.Right,val)}else{root.Left=insertIntoBST(root.Left,val)}return root
}

---

450.删除二叉搜索树中的节点

450.删除二叉搜索树中的节点

思路

确定单层递归的逻辑
这里就把二叉搜索树中删除节点遇到的情况都搞清楚。

有以下五种情况：

第一种情况：没找到删除的节点，遍历到空节点直接返回了
找到删除的节点
第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
着重考虑第五种情况。
时间复杂度On

代码

func deleteNode(root *TreeNode, key int) *TreeNode {if root==nil{return nil}if root.Val==key{if root.Left==nil{return root.Right}if root.Right==nil{return root.Left}temp:=root.Rightpre:=tempfor temp!=nil{pre=temptemp=temp.Left}pre.Left=root.Leftreturn root.Right}if root.Val<key{root.Right=deleteNode(root.Right,key)}if root.Val>key{root.Left=deleteNode(root.Left,key)}return root
}

困难

着重考虑删除节点的第五种情况。

temp:=root.Rightpre:=tempfor temp!=nil{pre=temptemp=temp.Left}pre.Left=root.Leftreturn root.Right

---

今日收获

了解了二叉搜索树只遍历一条边的递归方式。
了解了二叉搜索树的插入和删除。