【leetcode刷刷】235. 二叉搜索树的最近公共祖先 、701.二叉搜索树中的插入操作 、450.删除二叉搜索树中的节点

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

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 递归if not root: return if root.val == p.val: return pif root.val == q.val: return qleft = Noneright = Noneif root.val > p.val and root.val > q.val: left = self.lowestCommonAncestor(root.left, p, q)elif root.val < p.val and root.val < q.val:right = self.lowestCommonAncestor(root.right, p, q)else:left = self.lowestCommonAncestor(root.left, p, q)right = self.lowestCommonAncestor(root.right, p, q)if left and right: return rootif left: return leftif right: return rightreturn       

1. 自己写的时候，就是根据二叉树里的查找来写的逻辑，没有想到对于二叉搜索树而言，如果p/q在cur的两边，那么cur就是最近公共节点。想到这一点可以节约很多步骤。
2. 下面给出了精简版

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 递归if not root: return if root.val == p.val: return pif root.val == q.val: return q  # 这个也包括在剩余的情况里？if root.val > p.val and root.val > q.val: left = self.lowestCommonAncestor(root.left, p, q)if left: return leftelif root.val < p.val and root.val < q.val:right = self.lowestCommonAncestor(root.right, p, q)if right: return right# 剩下的就是在两边的，返回root就行。会不会存在两边都为None，那就找不到了，那也是rootreturn root

1. 但事实上这题用迭代法非常简单，判断条件返回就可以了。但是关键是，知道之前讲的二叉搜索树和最近公共节点的简便判断条件。

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':# 迭代法cur = rootwhile(cur):if cur.val < p.val and cur.val < q.val: cur = cur.rightelif cur.val > p.val and cur.val > q.val:cur = cur.leftelse:return cur

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

1. 一个简单的定义题？根据大小判断一下，保留前一个的指针，再插入就行

class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:# 二叉搜索树的插入if not root:return TreeNode(val)pre = Nonecur = rootwhile(cur):if val < cur.val:pre = curcur = cur.leftelse:pre = curcur = cur.rightprint(pre.val)if val < pre.val: pre.left = TreeNode(val)else:pre.right = TreeNode(val)return root

1. 用递归法也可以。大概想法就是如果小于cur，就递归左边，大于就递归右边，None的时候返回新节点就行。这样就不用pre来记录前一个了。

class Solution:def insertIntoBST(self, root, val):if root is None:node = TreeNode(val)return nodeif root.val > val:root.left = self.insertIntoBST(root.left, val)if root.val < val:root.right = self.insertIntoBST(root.right, val)return root

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

1. 脑袋已经递归晕了

class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:if not root:return root# 应该把删除节点的右节点的最左子节点提上来if root.val == key:if not root.left and not root.right:return Noneelif not root.left: return root.rightelif not root.right: return root.leftelse:cur = root.rightwhile cur.left is not None:cur = cur.leftcur.left = root.leftreturn root.rightelif root.val < key:root.right = self.deleteNode(root.right, key)else: # print(root.val)root.left = self.deleteNode(root.left, key)return root