给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
一般来说,删除节点可分为两个步骤:
Basically, the deletion can be divided into two stages:
说明: 要求算法时间复杂度为 O(h),h 为树的高度。
Note: Time complexity should be O(height of tree).
示例:
root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 5 / \ 4 6 / \ 2 7 另一个正确答案是 [5,2,6,null,4,null,7]。 5 / \ 2 6 \ \ 4 7
待删除节点在二叉树中的三种情况有:
另外二叉搜索树的中序遍历结果为从小到大顺序排列的; 删除节点如果不是叶子节点时, 则应把该节点的值替换为其右子树中最小的一个节点值 (删除节点的后驱节点); 删除节点如果不是叶子节点且无右子树时, 则应把该节点的值替换为其左子树中最大的一个节点值 (删除节点的前驱节点), 并在子树中递归删除刚刚替换的节点
你会发现, 二叉搜索树最小节点为该树的最左叶子; 最大节点为该树的最右叶子, 即:
class Solution { public TreeNode deleteNode(TreeNode root, int key) { if (root == null) return null; // 找到待删除节点后的三种情况 if (key == root.val) { // 删除节点为叶子节点 if (root.left == null && root.right == null) root = null; // 删除节点有右子树 else if (root.right != null) { root.val = postNode(root.right); root.right = deleteNode(root.right, root.val); } else {// 删除节点无右子树但存在左子树 root.val = preNode(root.left); root.left = deleteNode(root.left, root.val); } } else if (key > root.val) root.right = deleteNode(root.right, key); else root.left = deleteNode(root.left, key); return root; } // 找左子树的最大节点 private int preNode(TreeNode root) { while (root.right != null) root = root.right; return root.val; } // 找右子树的最小节点 private int postNode(TreeNode root) { while (root.left != null) root = root.left; return root.val; } }
class Solution: def deleteNode(self, root: TreeNode, key: int) -> TreeNode: if not root: return None # 找到待删除节点后的三种情况 if root.val == key: # 删除节点为叶子节点 if not root.left and not root.right: root = None # 删除节点有右子树 elif root.right: root.val = self.postNode(root.right) root.right = self.deleteNode(root.right, root.val) # 删除节点无右子树但存在左子树 else: root.val = self.preNode(root.left) root.left = self.deleteNode(root.left, root.val) elif key > root.val: root.right = self.deleteNode(root.right, key) else: root.left = self.deleteNode(root.left, key) return root # 找左子树的最大节点 def preNode(self, root: TreeNode) -> int: while root.right: root = root.right return root.val # 找右子树的最小节点 def postNode(self, root: TreeNode) -> int: while root.left: root = root.left return root.val
func deleteNode(root *TreeNode, key int) *TreeNode { if root == nil { return nil } // 找到待删除节点后的三种情况 if root.Val == key { // 删除节点为叶子节点 if root.Left == nil && root.Right == nil { root = nil } else if root.Right != nil {// 删除节点有右子树 root.Val = postNode(root.Right) root.Right = deleteNode(root.Right, root.Val) } else {// 删除节点无右子树但存在左子树 root.Val = preNode(root.Left) root.Left = deleteNode(root.Left, root.Val) } } else if key > root.Val { root.Right = deleteNode(root.Right, key) } else { root.Left = deleteNode(root.Left, key) } return root } // 找左子树的最大节点 func preNode(root *TreeNode) int { for root.Right != nil { root = root.Right } return root.Val } // 找右子树的最小节点 func postNode(root *TreeNode) int { for root.Left != nil { root = root.Left } return root.Val }
本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写Bug
原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。
原始发表时间:2020-03-23
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句