如何按层次遍历二叉树(儿子节点用Option<Box<TreeNode>>而不是Option<Rc<RefCell<TreeNode>>>,

darrenhp 发表于 2020-11-06 21:56


#[derive(PartialEq, Eq, Clone, Debug)]
 pub struct TreeNode {
     pub val: i32,
     pub left: Option<Box<TreeNode>>,
     pub right: Option<Box<TreeNode>>,
 }

 impl TreeNode {
     #[inline]
     fn new(val: i32) -> Self {
         TreeNode {
             val: val,
             left: None,
             right: None,
         }
     }
 }

评论区

写评论

AbdyCjen 2020-11-12 21:57

fn from_iter<'a, I: Iterator<Item=&'a str>>(mut it: I) -> Option<TreeNode> {
    let root_val = it.next().map(str::parse::<i32>)?.ok()?;
    let mut root = TreeNode::new(root_val);
    let mut dq = VecDeque::new();
    dq.push_back(&mut root.left);
    dq.push_back(&mut root.right);

    while let Some(no) = dq.pop_front() {
        if let Some(i) = it.next().map(|s| str::parse::<i32>(s).ok()).flatten() {
            *no = Some(Box::new(TreeNode::new(i)));
            let no = no.as_deref_mut().unwrap();
            dq.push_back(&mut no.left);
            dq.push_back(&mut no.right);
        }
    }

    Some(root)
}

fn main() {
    let v = vec!["1","2","3","#","#","4","#","#","5"];
    let tr: _ = from_iter(v.iter().copied());
    level_traverse(tr.as_ref().unwrap());
}

这样OK吗？

--
👇
darrenhp: 感谢！

另外请问一下，如果是根据层次遍历的结果 ”直接“重构这个二叉树能做到吗？

比如空指针用#表示

["1","2","3","#","#","4","#","#","5"] 表示

=========

我最开始是用数组先模拟一颗树，然后再用递归的方式构造的；但不知道能否有直接构造的办法（被所有权的转移关系卡住了）

作者 darrenhp 2020-11-11 16:44

感谢！

另外请问一下，如果是根据层次遍历的结果 ”直接“重构这个二叉树能做到吗？

比如空指针用#表示

["1","2","3","#","#","4","#","#","5"] 表示

=========

我最开始是用数组先模拟一颗树，然后再用递归的方式构造的；但不知道能否有直接构造的办法（被所有权的转移关系卡住了）

AbdyCjen 2020-11-08 00:50

use std::collections::VecDeque;
fn level_traverse(root: &TreeNode) {
    let mut dq = VecDeque::new();
    dq.push_back(Some(root));
    dq.push_back(None);
    let mut lev = 0;
    print!("{}:", lev);

    while let Some(no) = dq.pop_front() {
        if let Some(no) = no {
            if let Some(l) = no.left.as_deref() {
                dq.push_back(Some(l));
            }
            if let Some(r) = no.right.as_deref() {
                dq.push_back(Some(r));
            }
            print!("{},", no.val);
        } else if !dq.is_empty() {
            dq.push_back(None);
            lev += 1;
            print!("\n{}:", lev);
        }
    }
}

fn main() {
    let mut d = TreeNode::new(1);
    let mut left = TreeNode::new(2);
    left.left = Some(Box::new(TreeNode::new(4)));
    left.right = Some(Box::new(TreeNode::new(5)));
    d.left = Some(Box::new(left));
    d.right = Some(Box::new(TreeNode::new(3)));
    level_traverse(&d);
}

1 共 3 条评论, 1 页