深入Rust先序遍历（从零开始掌握二叉树的深度优先遍历）

例如，对于下面这棵二叉树：

        1       / \      2   3     / \    4   5

先序遍历的结果是：1 → 2 → 4 → 5 → 3

在 Rust 中定义二叉树

首先，我们需要用 Rust 定义一个二叉树节点。Rust 没有内置的树结构，但我们可以使用 Option<Box<TreeNode>> 来表示子节点（因为子节点可能为空）。

#[derive(Debug, Clone)]pub struct TreeNode {    pub val: i32,    pub left: Option<Box<TreeNode>>,    pub right: Option<Box<TreeNode>>,}impl TreeNode {    #[inline]    pub fn new(val: i32) -> Self {        TreeNode {            val,            left: None,            right: None,        }    }}

这里我们使用 Box 来在堆上分配节点，并用 Option 表示可能为空的子树。这是 Rust 中处理可空指针的安全方式。

递归实现先序遍历

最直观的方式是使用递归。由于 Rust 的所有权系统，我们需要小心地传递引用以避免移动值。

fn preorder_traversal_recursive(root: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {    if let Some(node) = root {        // 1. 访问根节点        result.push(node.val);        // 2. 递归遍历左子树        preorder_traversal_recursive(&node.left, result);        // 3. 递归遍历右子树        preorder_traversal_recursive(&node.right, result);    }}// 使用示例fn main() {    // 构建示例树    let mut root = Box::new(TreeNode::new(1));    root.left = Some(Box::new(TreeNode::new(2)));    root.right = Some(Box::new(TreeNode::new(3)));    root.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(4)));    root.left.as_mut().unwrap().right = Some(Box::new(TreeNode::new(5)));    let mut result = Vec::new();    preorder_traversal_recursive(&Some(root), &mut result);    println!("先序遍历结果: {:?}", result); // 输出: [1, 2, 4, 5, 3]}

注意：我们传入的是 &Option<Box<TreeNode>> 而不是 Option<Box<TreeNode>>，这样可以避免所有权转移，允许多次调用。

迭代实现先序遍历（使用栈）

虽然递归简洁，但在某些场景下（如深度很大的树），可能会导致栈溢出。因此，我们也可以用显式栈来实现迭代版本。

use std::collections::VecDeque;fn preorder_traversal_iterative(root: Option<Box<TreeNode>>) -> Vec<i32> {    let mut result = Vec::new();    let mut stack = VecDeque::new();        if let Some(node) = root {        stack.push_back(node);    }        while let Some(mut node) = stack.pop_back() {        result.push(node.val);                // 先压入右子树，再压入左子树（因为栈是后进先出）        if let Some(right) = node.right.take() {            stack.push_back(right);        }        if let Some(left) = node.left.take() {            stack.push_back(left);        }    }        result}

这里我们使用 VecDeque 作为栈。注意使用 take() 来获取子节点的所有权，这是 Rust 所有权机制的典型应用。

总结

通过本文，你已经学会了如何在 Rust 中实现Rust先序遍历。我们不仅掌握了递归和迭代两种方法，还深入理解了 Rust 如何通过其独特的所有权系统安全地处理树结构。

无论是面试准备、算法练习，还是实际项目开发，二叉树遍历都是必须掌握的基础技能。希望这篇教程能为你打下坚实的基础！

如果你对 Rust递归算法 或 Rust数据结构 感兴趣，不妨尝试实现中序遍历和后序遍历，进一步巩固所学知识。

Happy Coding with Rust! 🦀