1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| // @lc code=start
// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
/// ## 解题思路
/// - 递归
/// 1. 前序遍历又叫先根遍历, 其顺序为: 根节点->左子树->右子树;
/// 2. 由于是二叉搜索树,其左子树的所有节点值必然<根节点,而右子树的所有节点值>根节点值;
/// 3. 所有数组中的首元素为根节点, 而之后所有小于首元素的元素必然属于左子树,
/// 所有大于首元素的元素属于右子树;
/// 4. 所以查找数组中第一个>首元素的元素index, 即可将问题分解为更小规模;
pub fn bst_from_preorder(preorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
match preorder.len() {
0 => None,
1 => Some(Rc::new(RefCell::new(TreeNode::new(preorder[0])))),
_ => {
if let Some(p) = preorder.iter().position(|&x| x > preorder[0]) {
Some(Rc::new(RefCell::new(TreeNode {
val: preorder[0],
left: Solution::bst_from_preorder(preorder[1..p].to_vec()),
right: Solution::bst_from_preorder(preorder[p..].to_vec()),
})))
} else {
Some(Rc::new(RefCell::new(TreeNode {
val: preorder[0],
left: Solution::bst_from_preorder(preorder[1..].to_vec()),
right: None,
})))
}
}
}
}
}
// @lc code=end
|
