(js)leetcode 450. 删除二叉搜索树中的节点

╰+攻爆jí腚メ 2023-01-04 13:27 224阅读 0赞

题目:

给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。

一般来说,删除节点可分为两个步骤:

首先找到需要删除的节点;
如果找到了,删除它。
说明: 要求算法时间复杂度为 O(h),h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]
key = 3

  1. 5

/ \
3 6
/ \ \
2 4 7

给定需要删除的节点值是 3,所以我们首先找到 3 这个节点,然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。

  1. 5

/ \
4 6
/ \
2 7

另一个正确答案是 [5,2,6,null,4,null,7]。

  1. 5

/ \
2 6
\ \
4 7

思路:

  1. 节点为空,返回null

  2. 如果目标节点没有子节点,则直接删除,如果有一个非空子节点,则让该子节点代替自己的位置

  3. 若目标节点有两个子节点,则需要找到左子树中最小的那个节点,或者右子树中最大的节点代替自己的位置(本题中使用的是第二种)

代码实现:

  1. /**
  2. * Definition for a binary tree node.
  3. * function TreeNode(val, left, right) {
  4. * this.val = (val===undefined ? 0 : val)
  5. * this.left = (left===undefined ? null : left)
  6. * this.right = (right===undefined ? null : right)
  7. * }
  8. */
  9. /**
  10. * @param {TreeNode} root
  11. * @param {number} key
  12. * @return {TreeNode}
  13. */
  14. var deleteNode = function(root, key) {
  15. if(root == null) return null;
  16. if(root.val === key) {
  17. // 如果目标节点没有子节点,则直接删除,如果有一个非空子节点,则让该子节点代替自己的位置
  18. if(root.left === null) return root.right;
  19. if(root.right === null) return root.left;
  20. // 处理目标节点有两个子节点的情况
  21. let minNode = getMin(root.right);
  22. root.val = minNode.val;
  23. root.right = deleteNode(root.right, minNode.val);
  24. } else if(root.val > key) {
  25. root.left = deleteNode(root.left, key);
  26. } else if(root.val < key) {
  27. root.right = deleteNode(root.right, key);
  28. }
  29. return root;
  30. };
  31. var getMin = function(node) {
  32. // BST 最左边的就是最小的
  33. while(node.left !== null) node = node.left;
  34. return node;
  35. }

运行结果:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01fRXZl_size_16_color_FFFFFF_t_70

发表评论

表情:
评论列表 (有 0 条评论,224人围观)

还没有评论,来说两句吧...

相关阅读