Rust中如何为只读TreeNode实现带visited的非递归栈式DFS？

针对你遇到的问题，这里提供两种可行的实现方案，无需依赖节点值的唯一性，也能完美适配Rust中的Rc<RefCell<TreeNode>>结构：

方案一：无需额外visited集合（推荐） #

这种方法通过在栈中存储节点+访问标记的元组，彻底规避了跟踪已访问节点的需求，是迭代DFS的最优实现方式。

核心思路：

• 栈中每个元素是(节点引用, 是否已访问)的元组
• 首次弹出未标记的节点时，按DFS顺序将子节点入栈，再处理当前节点（调整入栈顺序可实现先序/中序/后序遍历）

以先序遍历为例，代码实现如下：

use std::rc::Rc;
use std::cell::RefCell;

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

fn dfs_preorder(root: Option<Rc<RefCell<TreeNode>>>) {
    let mut stack = vec![(root, false)];
    
    while let Some((node_opt, visited)) = stack.pop() {
        let node = match node_opt {
            Some(n) => n,
            None => continue,
        };
        
        if !visited {
            // 栈是后进先出，先入栈右子节点再入栈左子节点，保证左子节点优先处理
            stack.push((node.borrow().right.clone(), false));
            stack.push((node.borrow().left.clone(), false));
            // 先序遍历：立即处理当前节点
            println!("{}", node.borrow().val);
        }
        // 中序遍历：将处理节点代码移至else块，入栈顺序改为「右→当前（标记已访问）→左」
        // 后序遍历：将处理节点代码移至else块，入栈顺序改为「当前（标记已访问）→右→左」
    }
}

该方案优势：无需额外内存存储已访问节点，逻辑简洁，完全符合Rust安全规则，无原始指针操作。

方案二：使用visited集合（适配C++习惯） #

如果坚持要类似C++中存储指针的方式实现visited集合，可以通过获取TreeNode实例的原始内存地址作为唯一标识——每个Rc指向的TreeNode实例内存地址唯一（即使节点值相同），可用于跟踪已访问节点。

代码实现如下：

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashSet;
use std::ptr;

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

fn dfs_with_visited(root: Option<Rc<RefCell<TreeNode>>>) {
    let mut stack = Vec::new();
    let mut visited = HashSet::new();
    
    if let Some(root_node) = root {
        // 获取TreeNode的原始地址作为唯一标识
        let root_ptr = ptr::addr_of!(*root_node.borrow());
        stack.push(root_node);
        visited.insert(root_ptr);
        // 先序处理根节点
        println!("{}", stack.last().unwrap().borrow().val);
    }
    
    while let Some(node) = stack.last() {
        let node_ref = node.borrow();
        
        // 优先访问左子节点
        if let Some(left) = &node_ref.left {
            let left_ptr = ptr::addr_of!(*left.borrow());
            if !visited.contains(&left_ptr) {
                stack.push(left.clone());
                visited.insert(left_ptr);
                println!("{}", left.borrow().val);
                continue;
            }
        }
        
        // 左子节点已访问，访问右子节点
        if let Some(right) = &node_ref.right {
            let right_ptr = ptr::addr_of!(*right.borrow());
            if !visited.contains(&right_ptr) {
                stack.push(right.clone());
                visited.insert(right_ptr);
                println!("{}", right.borrow().val);
                continue;
            }
        }
        
        // 左右子节点均已访问，弹出当前节点
        stack.pop();
    }
}

这里使用std::ptr::addr_of!安全获取TreeNode实例的原始地址，既不违反Rust安全规则，又能实现类似C++指针的唯一标识功能。由于树是只读状态，borrow()不会出现可变借用冲突，无需担心panic。

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