代码随想录算法训练营day22 | 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

本文主要是介绍代码随想录算法训练营day22 | 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

二叉搜索树，如果p和q都小于当前节点，则继续搜索左子树；如果p和q都大于当前节点，则继续搜索右子树。如果p和q分别大于和小于当前节点，则当前节点为最近公共祖先

递归法

我在写代码时漏掉了左右的返回值，这样会导致递归后得到的节点传递不过来

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if not root or root.val == p.val or root.val == q.val:return rootif root.val < p.val and root.val < q.val:right = self.lowestCommonAncestor(root.right, p, q)if right:return rightelif root.val > p.val and root.val > q.val:left = self.lowestCommonAncestor(root.left, p, q)if left:return leftelse:return root

迭代法

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':while root:if root.val < p.val and root.val < q.val:root = root.rightelif root.val > p.val and root.val > q.val:root = root.leftelse:return root

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

递归法，有返回值

class Solution:def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if not root:return TreeNode(val)if root.val > val:root.left = self.insertIntoBST(root.left, val)if root.val < val:root.right = self.insertIntoBST(root.right, val)return root

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

递归法，有返回值，看完视频后各种情况都很清晰

class Solution:def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:# 没有找到要删除的结点if root is None:return None# 找到要删除的结点if root.val == key:if root.left is None and root.right is None:return Noneelif root.left is None:return root.rightelif root.right is None:return root.leftelse:cur = root.rightwhile cur.left:cur = cur.leftcur.left = root.leftreturn root.rightif root.val < key:root.right = self.deleteNode(root.right, key)if root.val > key:root.left = self.deleteNode(root.left, key)return root

这篇关于代码随想录算法训练营day22 | 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---