代码随想录 Day20 | 二叉树-part07（235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点）

今日总结BST的最近公共祖先、插入和删除题目235. 二叉搜索树的最近公共祖先题目链接题目题解第一想法利用二叉搜索树的性质查找一个节点的二进制编号共同前缀编号对应的节点为最近公共祖先。自己实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val x # self.left None # self.right None class Solution: def commonPrefix(self,a,b): # 求两个二进制字符串的共同前缀返回前缀对应的数值 bin_a bin(a)[2:] bin_b bin(b)[2:] i 0 while i len(bin_a) and i len(bin_b) and bin_a[i] bin_b[i]: i 1 if i 0: return 0 return int(bin_a[:i], 2) def getBinary(self,root,p): # 根据BST的值导航得到节点编号根为1 if not root:return 0 res 1 cur root while cur: if cur p: break elif cur.val p.val: res res * 2 cur cur.left else: res res * 2 1 cur cur.right return res def getNode(self,root,bin1): # 根据编号返回节点编号1 if not root: return None cur root bits bin1.bit_length() for i in range(bits-2,-1,-1): d (bin1 i) 1 if d 0: cur cur.left else: cur cur.right return cur def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: # 利用二叉搜索树的性质查找一个节点的编号 binp self.getBinary(root,p) # print(binp) binq self.getBinary(root,q) # print(binq) pre self.commonPrefix(binp,binq) # print(pre) if pre 0: return root return self.getNode(root,pre)时间复杂度O(h)平均 O(log n)最坏 O(n)空间复杂度O(1)学习题解方法1递归前序遍历单层递归的逻辑如果cur.val p.val and cur.val q.val 向左遍历如果返回值left不是None直接返回left。同理cur.val p.val and cur.val q.val向右遍历。否则返回当前节点。class Solution: def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) - TreeNode: if not root:return None if root.val p.val and root.val q.val: return self.lowestCommonAncestor(root.left,p,q) if root.val p.val and root.val q.val: return self.lowestCommonAncestor(root.right,p,q) return root时间复杂度O(h)空间复杂度O(n)方法2迭代法无需栈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.left elif root.val p.val and root.val q.val: root root.right else: return root return None时间复杂度O(h)空间复杂度O(1)701.二叉搜索树中的插入操作题目链接题目题解第一想法递归前序遍历。自己实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]: if not root: return TreeNode(val) if root.val val: root.right self.insertIntoBST(root.right,val) else: root.left self.insertIntoBST(root.left,val) return root时间复杂度O(h)最坏 O(n)平均 O(log n)空间复杂度O(h)学习题解递归函数可以不用返回值记录父节点parent找到要插入节点的位置让父节点指向插入节点。迭代法记录parent节点pre用于连接新的节点无需栈只需要更更新parent和cur指针。class Solution: def insertIntoBST(self, root: Optional[TreeNode], val: int) - Optional[TreeNode]: if not root: return TreeNode(val) parent None cur root while cur: parent cur if cur.val val: cur cur.left else: cur cur.right if parent.val val: parent.right TreeNode(val) # 左右勿反 else: parent.left TreeNode(val) return root时间复杂度O(h)空间复杂度O(1)450.删除二叉搜索树中的节点题目链接题目题解第一想法递归找到要删除的节点若有两个孩子则用左子树的最大值替换当前值并递归删除该最大值否则直接用非空孩子替代或返回None。自己实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def deleteNode(self, root: Optional[TreeNode], key: int) - Optional[TreeNode]: if not root: return None if root.val key: root.right self.deleteNode(root.right,key) elif root.val key: root.left self.deleteNode(root.left,key) else: # 找到要删除的节点 if not root.left and not root.right:return None # 不能用elif root.left or root.right: return root.left or root.right判断因为包括两个都有的情况 elif not root.left: return root.right elif not root.right: return root.left # 左右孩子都存在用左子树的最大值替换当前节点值 # 找到左子树的最大值节点即左子树中最右边的节点 # 注意左子树的最大值节点可能有左孩子 else: max_node root.left while max_node.right: max_node max_node.right # 找到左子树最大值 root.val max_node.val # 递归删除左子树最大值节点 root.left self.deleteNode(root.left,max_node.val) return root return root时间复杂度O(h)空间复杂度O(h)学习题解递归法1-值交换除了找左子树的最右边的节点前驱之外也可以找右子树最左边的节点后继。先交换要删除的节点的值和右子树最左节点的值然后递归删除右子树中要删除的节点值。class Solution: def deleteNode(self, root: Optional[TreeNode], key: int) - Optional[TreeNode]: if not root: return None if root.val key: root.right self.deleteNode(root.right,key) elif root.val key: root.left self.deleteNode(root.left,key) else: if not root.left: return root.right elif not root.right: return root.left else: cur root.right while cur.left: cur cur.left cur.left root.left return root.right return root递归法2-合并可以无需递归删除替换节点而是直接将要删除节点的节点的左子树整体挂到右子树的最左节点。会改变树的形状但是保持二叉搜索树的性质。迭代法1-辅助函数空间复杂度O(1)无需栈迭代找到待删除节点及其父节点然后调用辅助函数同解法一的合并逻辑得到新的子树再接到父节点上。辅助函数deleteOneNode也可用“值交换”实现。# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # self.val val # self.left left # self.right right class Solution: def deleteNode(self, root: Optional[TreeNode], key: int) - Optional[TreeNode]: def deleteOneNode(target): # 辅助函数删除给定节点返回合并后的新子树 if not target: return None if not target.right:return target.left # 将 target 的左子树挂到右子树的最左节点 cur target.right while cur.left: cur cur.left cur.left target.left return target.right if not root: return None # 迭代查找待删除节点及其父节点 cur root parent None while cur and cur.val!key: parent cur if cur.val key: cur cur.left else: cur cur.right if not cur: return root new_child deleteOneNode(cur) if not parent: return new_child if parent.left cur: parent.left new_child else: parent.right new_child return root今日收获二叉搜索树的最近公共祖先利用节点值的大小关系从根向下搜索。若当前节点值同时大于 p 和 q则 LCA 在左子树同时小于则在右子树否则当前节点即为 LCA。无需像普通二叉树那样记录路径或回溯。二叉搜索树的插入操作根据 BST 性质找到合适的空位置叶子节点的左或右插入新节点。迭代法不需要栈只需记录父节点。二叉搜索树的删除操作最复杂需分四种情况叶子节点直接返回 None。只有左孩子返回左子树。只有右孩子返回右子树。左右孩子都存在两种经典方法值交换法找到左子树的最大节点前驱或右子树的最小节点后继将其值复制到待删除节点然后递归删除那个前驱/后继节点。合并法将待删除节点的左子树整体挂到右子树的最左节点即右子树中最小值节点的左孩子然后返回右子树作为新子树。此方法改变了树的形状但保持 BST 性质。学习时长2.5h模板235. BST 最近公共祖先迭代def lowestCommonAncestor(root, p, q): while root: if root.val p.val and root.val q.val: root root.left elif root.val p.val and root.val q.val: root root.right else: return root return None701. BST 插入迭代def insertIntoBST(root, val): if not root: return TreeNode(val) cur, parent root, None while cur: parent cur if cur.val val: cur cur.left else: cur cur.right if parent.val val: parent.left TreeNode(val) else: parent.right TreeNode(val) return root450. BST 删除递归 - 值交换法def deleteNode(root, key): if not root: return None if root.val key: root.left deleteNode(root.left, key) elif root.val key: root.right deleteNode(root.right, key) else: # 找到要删除的节点 if not root.left: return root.right if not root.right: return root.left # 左右孩子都在找左子树的最大值前驱 max_node root.left while max_node.right: max_node max_node.right root.val max_node.val root.left deleteNode(root.left, max_node.val) return root450. BST 删除递归 - 合并法简洁def deleteNode(root, key): if not root: return None if root.val key: root.left deleteNode(root.left, key) elif root.val key: root.right deleteNode(root.right, key) else: if not root.left: return root.right if not root.right: return root.left # 将左子树挂到右子树的最左节点 cur root.right while cur.left: cur cur.left cur.left root.left return root.right return root易错点235 题不要试图为每个节点编二进制编号那样复杂且容易出错。直接利用值比较即可。701 题迭代插入时必须记录父节点否则无法连接新节点。注意最后判断新节点应挂在父节点的左还是右。450 题删除节点时如果左右孩子都存在不能简单返回其中一个子树否则会丢失另一子树。值交换法替换值后必须递归删除那个前驱/后继节点注意该节点可能有左孩子无右孩子。合并法将左子树挂到右子树最左节点后返回的是root.right不要忘记处理root.left已经挂到别处。注意递归删除前驱/后继节点时调用deleteNode(root.left, max_node.val)参数是左子树的根而不是root。所有 BST 操作的时间复杂度都与树的高度有关平均 O(log n)最坏 O(n)链状树。