Leetcode: Delete Node in a BST
2023-09-11 14:14:07 时间
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: Search for a node to remove. If the node is found, delete the node. Note: Time complexity should be O(height of tree). Example: root = [5,3,6,2,4,null,7] key = 3 5 / \ 3 6 / \ \ 2 4 7 Given key to delete is 3. So we find the node with value 3 and delete it. One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \ 2 7 Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7
recursively find the node that needs to be deleted
Once the node is found, have to handle the below 4 cases
- node doesn't have left nor right - return null
- node only has left subtree- return the left subtree
- node only has right subtree- return the right subtree
- node has both left and right - find the minimum value in the right subtree, set that value to the currently found node, then recursively delete the minimum value in the right subtree
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode(int x) { val = x; } 8 * } 9 */ 10 public class Solution { 11 public TreeNode deleteNode(TreeNode root, int key) { 12 if (root == null) return null; 13 if (key < root.val) { 14 root.left = deleteNode(root.left, key); 15 } 16 else if (key > root.val) { 17 root.right = deleteNode(root.right, key); 18 } 19 else { //k == root.val 20 if (root.left == null) return root.right; 21 else if (root.right == null) return root.left; 22 else { // both root.left and root.right are not null 23 TreeNode minRight = findMin(root.right); 24 root.val = minRight.val; 25 root.right = deleteNode(root.right, minRight.val); 26 } 27 } 28 return root; 29 } 30 31 public TreeNode findMin(TreeNode cur) { 32 while (cur.left != null) { 33 cur = cur.left; 34 } 35 return cur; 36 } 37 }
相关文章
- Leetcode: Delete Node in a Linked List
- Leetcode: Dungeon Game
- Leetcode: 3Sum Closest
- Node.js: Python not found exception due to node-sass and node-gyp
- [LeetCode] Remove Nth Node From End of List
- LeetCode 912. 排序数组
- 69、【哈希表】leetcode——202. 快乐数(C++版本)
- 【leetcode】日积月累,每日一题--24. 两两交换链表中的节点(DayDayUp 14)
- 【LeetCode】237. Delete Node in a Linked List
- [Leetcode]-String to Integer (atoi)
- LeetCode——Remove Nth Node From End of List
- [LeetCode] 1019. Next Greater Node In Linked List 链表中的下一个较大的结点
- [LeetCode] Second Minimum Node In a Binary Tree 二叉树中第二小的结点
- [LeetCode] Valid Triangle Number 合法的三角形个数
- [LeetCode] The Maze III 迷宫之三
- [LeetCode] 450. Delete Node in a BST 删除二叉搜索树中的节点
- [LeetCode] 382. Linked List Random Node 链表随机结点
- [LeetCode] 327. Count of Range Sum 区间和计数
- [LeetCode] 222. Count Complete Tree Nodes 求完全二叉树的节点个数
- Leetcode——24. Swap Nodes in Pairs
- leetcode算法155.最小栈
- leetcode算法67.二进制求和