给定一棵二叉搜索树的根节点和一个插入值 val。请你把这个 val 插入二叉搜索树中并保持这棵树依然是二叉搜索树。你可以返回任意一个合法结果。
例如:输入二叉树
,插入一个 4 ,可能的结果有
,
等等,返回任意一个即可。
数据范围:二叉搜索树节点数满足
,二叉搜索树上节点值满足 ![](https://www.nowcoder.com/equation?tex=1%20%5Cle%20val%20%5Cle%2010%5E9%20%5C)
/** * #[derive(PartialEq, Eq, Debug, Clone)] * pub struct TreeNode { * pub val: i32, * pub left: Option<Box<TreeNode>>, * pub right: Option<Box<TreeNode>>, * } * * impl TreeNode { * #[inline] * fn new(val: i32) -> Self { * TreeNode { * val: val, * left: None, * right: None, * } * } * } */ struct Solution{ } type T = Option<Box<TreeNode>>; use std::cmp::Ordering::{Less, Equal, Greater}; impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param root TreeNode类 * @param val int整型 * @return TreeNode类 */ pub fn insertToBST(&self, mut root: T, val: i32) -> T { // write code here if root.is_none() { Some(Box::new(TreeNode::new(val))) } else { Self::insert(&mut root, val); root } } fn insert(mut node: &mut T, val: i32){ loop { match val.cmp(&node.as_ref().unwrap().val) { Less => { if node.as_mut().unwrap().left.is_none() { node.as_mut().unwrap().left = Some(Box::new(TreeNode::new(val))); break; } else { node = &mut node.as_mut().unwrap().left; } }, Greater => { if node.as_mut().unwrap().right.is_none() { node.as_mut().unwrap().right = Some(Box::new(TreeNode::new(val))); break; } else { node = &mut node.as_mut().unwrap().right; } }, Equal => { todo!(); }, }; }; } }