Rust中二进制树的广度首次遍历

Question

我是Rust的新手，但来自C++，我觉得类型系统的体操有点。。。令人不安。我用LeetCode的问题来自学Rust。采用以下二叉树的定义：

pub struct TreeNode {
pub val: i32,
pub left: Option<Rc<RefCell<TreeNode>>>,
pub right: Option<Rc<RefCell<TreeNode>>>,
}

好吧，这已经有点难看了，但我有点理解原因(尽管我不清楚为什么我们不能有一个单独的类型来组合Option、Rc和RefCell的功能，而这些功能似乎经常同时出现(。

无论如何，这是我实现的BFS算法(它没有做任何有趣的事情，重点是总体布局(：

use std::collections::VecDeque;
fn bfs(root: Option<Rc<RefCell<TreeNode>>>) {
let mut queue = VecDeque::new();
queue.push_back((root, 0));
while queue.len() > 0 {
// 'pos' measures how far out to the left or right the given node is.
let (node, pos) = queue.pop_front().unwrap();
if node.is_none() { continue; }
let subtree = node.unwrap();
queue.push_back((subtree.borrow().left.clone(), pos - 1));
queue.push_back((subtree.borrow().right.clone(), pos + 1));
}
}

我的问题是：Rust真的是这样做的吗？难道没有一种更独特(更简洁(的方法来做到这一点吗？我的意思是，代码使用unwrap()、borrow()和clone()中的一个来获取左右树指针。至少可以说，这感觉有点麻烦。这可能是Rust中的总体做法，但我很好奇这是常态还是例外？

Answer 1

这里的unwrap()确实是非惯用的，可以替换。第一个unwrap()可以用while let代替，第二个用if let:代替

while let Some((node, pos)) = queue.pop_front() {
// 'pos' measures how far out to the left or right the given node is.
if let Some(subtree) = node {
queue.push_back((subtree.borrow().left.clone(), pos - 1));
queue.push_back((subtree.borrow().right.clone(), pos + 1));
}
}

不得不用if let包裹整个环体是不幸的。实验特征let_else将解决(在Rust 1.65.0中稳定(：

#![feature(let_else)]
while let Some((node, pos)) = queue.pop_front() {
// 'pos' measures how far out to the left or right the given node is.
let Some(subtree) = node else {
continue;
};

queue.push_back((subtree.borrow().left.clone(), pos - 1));
queue.push_back((subtree.borrow().right.clone(), pos + 1));
}

但borrow()和clone()是因为您试图绕过Rc<RefCell>的所有权规则。这在某种程度上被认为是一种反模式：如果您认为需要使用它，请三思。也许还有更为粗鲁的做事方式。有时它很简单，有时需要重新设计数据结构(例如，Rust中通常用索引表示的图(。

更简单的树也将具有更简单的搜索功能：

pub struct TreeNode {
pub val: i32,
pub left: Option<Box<TreeNode>>,
pub right: Option<Box<TreeNode>>,
}
fn bfs(root: Option<&TreeNode>) {
let mut queue = VecDeque::new();
queue.push_back((root, 0));
while let Some((node, pos)) = queue.pop_front() {
// 'pos' measures how far out to the left or right the given node is.
let Some(subtree) = node else {
continue;
};

queue.push_back((subtree.left.as_deref(), pos - 1));
queue.push_back((subtree.right.as_deref(), pos + 1));
}
}