如何在Rust中实现不移动根节点的二叉树前序遍历函数？

作为Rust新手，我在学习《Rust官方书籍》后尝试实现二叉树的前序遍历，编写了如下代码，但首次调用遍历函数后根节点被移动，导致第二次调用失败：

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}
impl TreeNode {
    fn new(val: i32, left: Option<Box<TreeNode>>, right: Option<Box<TreeNode>>) -> TreeNode {
        TreeNode { val, left, right }
    }
}
fn main() {
    let root = TreeNode::new(
        120,
        Some(Box::new(TreeNode::new(
            150,
            Some(Box::new(TreeNode::new(180, None, None))),
            Some(Box::new(TreeNode::new(40, None, None))),
        ))),
        Some(Box::new(TreeNode::new(
            110,
            Some(Box::new(TreeNode::new(144, None, None))),
            None,
        ))),
    );
    pre_order(Some(Box::new(root)));
    pre_order(Some(Box::new(root))); // 编译错误：root已被移动
}
fn pre_order(root: Option<Box<TreeNode>>) {
    match root {
        None => {
            return;
        }
        Some(root_node) => {
            println!("{} ", root_node.val);
            pre_order(root_node.left);
            pre_order(root_node.right);
        }
    }
}

我尝试通过添加引用解决所有权问题，但错误地给所有类型都加了引用，修改后的函数和调用代码如下：

fn pre_order(root: &Option<&Box<&TreeNode>>) {
    match root {
        None => {
            return;
        }
        Some(root_node) => {
            println!("{} ", root_node.val);
            pre_order(&&&root_node.left);
            pre_order(&&&root_node.right);
        }
    }
}

调用方式：

pre_order(&Some(&Box::new(&root)));
pre_order(&Some(&Box::new(&root)));

但出现类型不匹配错误：

error[E0308]: mismatched types
  --> src/main.rs:35:23
   |
35 |             pre_order(&&&root_node.left);
   |             --------- ^^^^^^^^^^^^^^^^^ expected enum `Option`, found reference
   |             |
   |             arguments to this function are incorrect
   |
   = note: expected reference `&Option<&Box<&TreeNode>>`
              found reference `&&&Option<Box<TreeNode>>`
note: function defined here
  --> src/main.rs:28:4
   |
28 | fn pre_order(root: &Option<&Box<&TreeNode>>) {
   |    ^^^^^^^^^ ------------------------------

error[E0308]: mismatched types
  --> src/main.rs:36:23
   |
36 |             pre_order(&&&root_node.right);
   |             --------- ^^^^^^^^^^^^^^^^^^ expected enum `Option`, found reference
   |             |
   |             arguments to this function are incorrect
   |
   = note: expected reference `&Option<&Box<&TreeNode>>`
              found reference `&&&Option<Box<TreeNode>>`
note: function defined here
  --> src/main.rs:28:4
   |
28 | fn pre_order(root: &Option<&Box<&TreeNode>>) {
   |    ^^^^^^^^^ ------------------------------

我需要解决：如何正确设计pre_order函数，在不消耗节点的前提下递归传递引用？是否需要Rc、RefCell或生命周期标注？

正确实现方案：传递单一层次的引用 #

你不需要使用Rc、RefCell这类高级特性——因为这里只是只读遍历，没有共享可变数据的需求，仅通过普通引用就能解决所有权问题。核心是只在最外层的Option<Box<TreeNode>>上添加一层引用，而不是嵌套多层引用。

修改后的pre_order函数：

fn pre_order(root: &Option<Box<TreeNode>>) {
    match root {
        None => return,
        Some(node) => {
            // Box<T>会自动解引用为T，所以可以直接访问node.val
            println!("{} ", node.val);
            // 递归传递left/right的引用，无需额外嵌套
            pre_order(&node.left);
            pre_order(&node.right);
        }
    }
}

对应的main函数调整：

fn main() {
    let root = TreeNode::new(
        120,
        Some(Box::new(TreeNode::new(
            150,
            Some(Box::new(TreeNode::new(180, None, None))),
            Some(Box::new(TreeNode::new(40, None, None))),
        ))),
        Some(Box::new(TreeNode::new(
            110,
            Some(Box::new(TreeNode::new(144, None, None))),
            None,
        ))),
    );
    // 将root包装为Option<Box<TreeNode>>，之后传递它的引用
    let tree = Some(Box::new(root));
    pre_order(&tree);
    pre_order(&tree); // 现在可以正常调用两次
}

为什么这个方案可行？ #

1. 所有权保留：传递&Option<Box<TreeNode>>时，我们只是借用了这个Option的引用，不会转移所有权，因此可以多次调用pre_order。
2. 自动解引用：Box<TreeNode>实现了Deref trait，所以Some(node)中的node会自动解引用为TreeNode的引用，直接访问node.val和node.left/node.right都是合法的。
3. 递归一致性：node.left和node.right本身就是Option<Box<TreeNode>>类型，取它们的引用&node.left正好匹配函数参数&Option<Box<TreeNode>>，无需额外的引用嵌套。

更简洁的优化：直接传递TreeNode的引用 #

如果想进一步简化，还可以让函数直接接收Option<&TreeNode>类型，这样避免处理Box的细节，代码更清晰：

fn pre_order(root: Option<&TreeNode>) {
    if let Some(node) = root {
        println!("{} ", node.val);
        // 将left/right转换为Option<&TreeNode>：用as_ref()获取Box内部的引用
        pre_order(node.left.as_ref().map(|b| b.as_ref()));
        pre_order(node.right.as_ref().map(|b| b.as_ref()));
    }
}

调用方式调整为：

fn main() {
    let root = TreeNode::new(
        120,
        Some(Box::new(TreeNode::new(
            150,
            Some(Box::new(TreeNode::new(180, None, None))),
            Some(Box::new(TreeNode::new(40, None, None))),
        ))),
        Some(Box::new(TreeNode::new(
            110,
            Some(Box::new(TreeNode::new(144, None, None))),
            None,
        ))),
    );
    pre_order(Some(&root));
    pre_order(Some(&root)); // 直接传递root的引用
}

这个版本利用Option::as_ref()将Option<Box<TreeNode>>转换为Option<&Box<TreeNode>>，再通过Box::as_ref()转换为Option<&TreeNode>，同样实现了无所有权消耗的遍历。

内容的提问来源于stack exchange，提问作者ArchBug