Rust向量转完全二叉树代码修复求助：多元素输入失效

你的代码确实是take()方法的使用顺序导致了问题：当从前往后遍历节点时，父节点会通过take()把子节点从vector中移走（原位置变为None），等到后续循环到该子节点的索引时，它已经是None，无法再作为父节点设置自己的子节点。比如处理第0个节点时，会把第1、2个节点移走，当循环到第1个节点时，tree[1]已经是空的，自然无法绑定它的子节点（第3、4个）。

修复方案 #

调整遍历顺序，从最后一个非叶子节点开始向前遍历。完全二叉树中，最后一个非叶子节点的索引是(len - 2) / 2（整数除法）。这样处理父节点时，子节点还在vector中，且后续不会再以这些子节点的索引作为父节点遍历（因为我们是从后往前），完美避免了所有权转移带来的问题。

修改后的完整代码：

#[derive(Debug)]
pub struct TreeNode<T> {
    pub value: T,
    pub left: Option<Box<TreeNode<T>>>,
    pub right: Option<Box<TreeNode<T>>>,
}

pub fn construct_tree<T: Copy>(input: Vec<Option<T>>) -> Option<Box<TreeNode<T>>> {
    if input.is_empty() {
        return None;
    }

    // 先批量创建所有节点的Option包装
    let mut nodes: Vec<Option<Box<TreeNode<T>>>> = input
        .into_iter()
        .map(|val| val.map(|v| Box::new(TreeNode {
            value: v,
            left: None,
            right: None,
        })))
        .collect();

    let len = nodes.len();
    // 从最后一个非叶子节点倒序遍历到根节点
    for i in (0..=(len - 2) / 2).rev() {
        if let Some(ref mut node) = nodes[i] {
            // 绑定左子节点
            let left_idx = 2 * i + 1;
            if left_idx < len {
                node.left = nodes[left_idx].take();
            }
            // 绑定右子节点
            let right_idx = 2 * i + 2;
            if right_idx < len {
                node.right = nodes[right_idx].take();
            }
        }
    }

    // 取出根节点返回
    nodes.into_iter().next().unwrap_or(None)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_small_tree() {
        let tree1 = construct_tree(vec![Some(3), Some(9), Some(20)]);
        println!("{:?}", tree1.unwrap());
    }

    #[test]
    fn test_larger_tree() {
        let tree2 = construct_tree(vec![Some(3), Some(9), Some(20), Some(15), Some(7)]);
        println!("{:?}", tree2.unwrap());
    }

    #[test]
    fn test_full_tree() {
        let tree3 = construct_tree(vec![Some(1), Some(2), Some(3), Some(4), Some(5), Some(6), Some(7)]);
        println!("{:?}", tree3.unwrap());
    }
}

关键修改说明 #

1. 遍历顺序调整：倒序遍历非叶子节点，确保父节点处理时，子节点还在vector中，且后续不会再被当作父节点处理。
2. 简化逻辑：移除了单独处理长度为1的分支，通用逻辑已覆盖该场景。
3. 所有权正确转移：保留take()方法，它能安全地将子节点的所有权转移给父节点，而原位置的None不会再被访问，避免了无效操作。

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