450. Delete Node in a BST Medium

1/**
2 * [450] Delete Node in a BST
3 *
4 * 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.
5 * Basically, the deletion can be divided into two stages:
6 * <ol>
7 * 	Search for a node to remove.
8 * 	If the node is found, delete the node.
9 * </ol>
10 *  
11 * Example 1:
12 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/04/del_node_1.jpg" style="width: 800px; height: 214px;" />
13 * Input: root = [5,3,6,2,4,null,7], key = 3
14 * Output: [5,4,6,2,null,null,7]
15 * Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
16 * One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
17 * Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
18 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/04/del_node_supp.jpg" style="width: 350px; height: 255px;" />
19 * 
20 * Example 2:
21 * 
22 * Input: root = [5,3,6,2,4,null,7], key = 0
23 * Output: [5,3,6,2,4,null,7]
24 * Explanation: The tree does not contain a node with value = 0.
25 * 
26 * Example 3:
27 * 
28 * Input: root = [], key = 0
29 * Output: []
30 * 
31 *  
32 * Constraints:
33 * 
34 * 	The number of nodes in the tree is in the range [0, 10^4].
35 * 	-10^5 <= Node.val <= 10^5
36 * 	Each node has a unique value.
37 * 	root is a valid binary search tree.
38 * 	-10^5 <= key <= 10^5
39 * 
40 *  
41 * Follow up: Could you solve it with time complexity O(height of tree)?
42 * 
43 */
44pub struct Solution {}
45use crate::util::tree::{TreeNode, to_tree};
46
47// problem: https://leetcode.com/problems/delete-node-in-a-bst/
48// discuss: https://leetcode.com/problems/delete-node-in-a-bst/discuss/?currentPage=1&orderBy=most_votes&query=
49
50// submission codes start here
51
52// Definition for a binary tree node.
53// #[derive(Debug, PartialEq, Eq)]
54// pub struct TreeNode {
55//   pub val: i32,
56//   pub left: Option<Rc<RefCell<TreeNode>>>,
57//   pub right: Option<Rc<RefCell<TreeNode>>>,
58// }
59// 
60// impl TreeNode {
61//   #[inline]
62//   pub fn new(val: i32) -> Self {
63//     TreeNode {
64//       val,
65//       left: None,
66//       right: None
67//     }
68//   }
69// }
70use std::rc::Rc;
71use std::cell::RefCell;
72impl Solution {
73    pub fn delete_node(root: Option<Rc<RefCell<TreeNode>>>, key: i32) -> Option<Rc<RefCell<TreeNode>>> {
74        Some(Rc::new(RefCell::new(TreeNode::new(0))))
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_450() {
86    }
87}
88