caibirdme
commented
4 years ago Convert Sorted List to Binary Search Tree 把一个有序链表转成平衡二叉搜索树。想想一下，如果我们已经有了这颗BST，那么我们对它进行中序遍历，结果就是题目给的链表。我们可以尝试遍历这颗虚拟的树。回想一下怎么在0..n初始化一颗线段树，同样的做法。只是我们使用中序遍历。
fn in_order(head: &mut Option<Box<ListNode>>, l: usize, r: usize) -> Option<Rc<RefCell<TreeNode>>> {
if l == r {
let node = TreeNode::new(head.as_ref().unwrap().val);
*head = head.take().unwrap().next;
return Some(Rc::new(RefCell::new(node)));
}
let mid = (l+r) / 2;
let lch = {
if mid > l {
Self::in_order(head, l, mid-1)
} else {
None
}
};
let mut root = TreeNode::new(head.as_ref().unwrap().val);
*head = head.take().unwrap().next;
root.left = lch;
root.right = Self::in_order(head, mid+1, r);
Some(Rc::new(RefCell::new(root)))
}
go over linked-list related problems