这道题目要求对二叉树进行锯齿形Zigzag层序遍历即第 1 层从左到右第 2 层从右到左第 3 层从左到右以此类推…最直观的解法是广度优先搜索BFS配合队列只需在普通层序遍历的基础上根据当前层的方向标志决定是否反转即可。解题思路队列辅助使用“VecDeque” 作为队列存储“RcRefCell” 智能指针LeetCode Rust 环境的标准定义。方向标志用“left_to_right” 布尔变量标记当前层的遍历方向初始为“true”。分层处理记录当前队列长度即该层节点数。依次出队节点将其值加入当前层数组。将左右子节点入队。如果该层是从右到左“left_to_right” 为“false”则将当前层数组反转。切换方向每处理完一层翻转“left_to_right”。Rust 代码实现注以下代码包含了 LeetCode 中已定义的“TreeNode” 结构体方便你在本地调试在 LeetCode 提交时只需提交“impl Solution” 部分。use std::cell::RefCell;use std::rc::Rc;use std::collections::VecDeque;// LeetCode 定义的 TreeNode本地调试时可取消注释// #[derive(Debug, PartialEq, Eq)]// pub struct TreeNode {// pub val: i32,// pub left: OptionRcRefCell,// pub right: OptionRcRefCell,// }//// impl TreeNode {// #[inline]// pub fn new(val: i32) - Self {// TreeNode { val, left: None, right: None }// }// }impl Solution {pub fn zigzag_level_order(root: OptionRcRefCell) - VecVec {let mut result: VecVec Vec::new();// 边界条件根节点为空 let root match root { Some(r) r, None return result, }; let mut queue: VecDequeRcRefCellTreeNode VecDeque::new(); queue.push_back(root); let mut left_to_right true; // 当前层是否从左到右 while !queue.is_empty() { let level_size queue.len(); let mut current_level: Veci32 Vec::new(); for _ in 0..level_size { // 出队 let node queue.pop_front().unwrap(); let node_ref node.borrow(); // 将当前节点值加入当前层先统一从左到右 push current_level.push(node_ref.val); // 左右子节点入队 if let Some(ref left) node_ref.left { queue.push_back(left.clone()); } if let Some(ref right) node_ref.right { queue.push_back(right.clone()); } } // 如果是从右到左的层则反转当前层结果 if !left_to_right { current_level.reverse(); } result.push(current_level); left_to_right !left_to_right; // 切换方向 } result }}复杂度分析时间复杂度O(n)每个节点恰好被访问一次。“Vec::reverse()” 的时间复杂度是 O(k)k 为该层节点数总体仍为 O(n)。空间复杂度O(n)队列最多存储一层的节点最坏情况约 n/2结果数组存储所有节点值。示例测试本地运行版fn main() {// 构建示例二叉树:// 3// /// 9 20// /// 15 7let root Rc::new(RefCell::new(TreeNode::new(3))); let left Rc::new(RefCell::new(TreeNode::new(9))); let right Rc::new(RefCell::new(TreeNode::new(20))); let right_left Rc::new(RefCell::new(TreeNode::new(15))); let right_right Rc::new(RefCell::new(TreeNode::new(7))); right.borrow_mut().left Some(right_left); right.borrow_mut().right Some(right_right); root.borrow_mut().left Some(left); root.borrow_mut().right Some(right); let result Solution::zigzag_level_order(Some(root)); println!({:?}, result); // 输出: [[3], [20, 9], [15, 7]]} 小提示如果你希望避免使用“reverse”虽然不影响时间复杂度也可以使用“VecDeque” 作为“current_level” 的容器从左到右时“push_back”从右到左时push_front最后再转成“Vec” 存入“result”。需要我帮你把这段代码转成其他语言或者讲解如何用迭代 DFS 实现吗