给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点;
如果找到了,删除它。
示例 1:
输入:root = [5,3,6,2,4,null,7], key = 3
输出:[5,4,6,2,null,null,7]
解释:给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0
输出: []
提示:
节点数的范围 [0, 104].
-105 <= Node.val <= 105
节点值唯一
root 是合法的二叉搜索树
-105 <= key <= 105
进阶: 要求算法时间复杂度为 O(h),h 为树的高度。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/delete-node-in-a-bst
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
麻烦的地方在于删除后继续保持二叉搜索树的性质。
class Solution { public TreeNode deleteNode (TreeNode root, int key) { if (root == null) { return null; } // 对根结点进行判断,避开父节点为 null 的情况。 if (root.val == key) { if (root.left == null && root.right == null) { return null; } else if (root.left == null) { return root.right; } else if (root.right == null) { return root.left; } getLeftLeaf(root.right).left = root.left; return root.right; } else { dfs(root, null, key, true); } return root; } // @direction 该节点为父节点的左子树还是右子树,true 为左,false 为右。 private void dfs (TreeNode root, TreeNode parent, int key, boolean direction) { // 不包含 key if (root == null) { return; } if (root.val > key) { dfs(root.left, root, key, true); } else if (root.val < key) { dfs(root.right, root, key, false); } else { // 找到 key 所在节点 // 第一种情况:目标节点的左右节点都为 null if (root.left == null && root.right == null) { if (direction) { parent.left = null; } else { parent.right = null; } // 第二种情况:目标节点的左右节点都不为 null,此时将目标节点的左子树放到右子树最左边的叶子节点,然后将该节点删除即可(参考第三,第四种情况)。 } else if (root.left != null && root.right != null) { getLeftLeaf(root.right).left = root.left; if (direction) { parent.left = root.right; } else { parent.right = root.right; } // 第三种情况:目标节点的左节点为 null,此时将右子树直接替代目标节点即可。 } else if (root.left == null) { if (direction) { parent.left = root.right; } else { parent.right = root.right; } // 第四种情况:目标节点的右节点为 null,此时将左子树直接替代目标节点即可。 } else { if (direction) { parent.left = root.left; } else { parent.right = root.left; } } } } // 寻找目标节点右子树最左边的节点。 private TreeNode getLeftLeaf (TreeNode root) { if (root.left == null) { return root; } else { return getLeftLeaf(root.left); } } }