今日签到题迷惑，怎么把迭代器存进结构体里和怎么写闭包递归？

lithbitren 发表于 2020-05-22 16:38

Tags：leetcode,语法,闭包,递归,迭代器,生命周期

今日leetcode签到题，大意就是根据二叉树的前序遍历和中序遍历生成二叉树。

这个是我的题解： https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/di-gui-sheng-cheng-shu-zhi-chuan-zhong-xu-shu-lie-/

py老早就过了，预处理一个坐标逆映射数组再加上前序遍历迭代器以及闭包递归就行，代码也不复杂。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        p, d = iter(preorder), {j: i for i, j in enumerate(inorder)}
        def f(i, j):
            if i < j:
                t = TreeNode(next(p))
                t.left = f(i, d[t.val])
                t.right = f(d[t.val] + 1, j)
                return t
        return f(0, len(inorder))

但翻译成rust就苦手了，闭包递归在StackOverflow上看到一个阶乘的写法，放到这就怎么都通不过，而且知道rust闭包的原理会自动生成结构体，本质跟外部调用没太大区别，于是就把参数写进结构体里面了，虽然外部递归通过了，但还是想知道闭包递归咋写的。

如果不用迭代器的话，直接就通过了，但还是试了下迭代器，发现结构体里内的迭代器生命周期真不知道咋标记，怎么标都通过不了，在此向各位大佬求助指点。

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Data {
            i: 0,
            p: preorder,
            // p: preorder.iter(), //把迭代器存进结构体
            d: inorder.iter().enumerate().map(|(i, &j)| (j, i)).collect()
        }.f(0, inorder.len())
    }
}

struct Data {
    i: usize,
    p: Vec<i32>,
    // p: std::slice::Iter<'_, i32>, 
    //这里的生命周期不知道咋标，在struct和impl上标来标去要不编译不通过，要不说生命周期不够长。。
    d: std::collections::HashMap<i32, usize>
}

impl Data {
    fn f(&mut self, i: usize, j: usize) -> Option<Rc<RefCell<TreeNode>>> {
        if i < j {
            let mut t = TreeNode::new(self.p[self.i]);
            // let mut t = TreeNode::new(self.p.next().unwrap());
            self.i += 1;
            t.left = self.f(i, self.d[&t.val]);
            t.right = self.f(self.d[&t.val] + 1, j);
            return Some(Rc::new(RefCell::new(t)))
        } 
        None
    }
}

评论区

写评论

作者 lithbitren 2020-05-23 15:37

谢谢解惑，大致明白了。

对以下内容的回复：

xjkdev 2020-05-23 15:19

IntoIter不用生命周期，是因为IntoIter直接调用是会move掉Vec的，要引用的话应该用(&preorder).into_iter()或(&mut preorder).into_iter()，就需要标记周期了。

其二，结构体不能用是因为'_这个标签目前只能在函数里使用吧，毕竟结构体本身存储有数据，生命周期会更复杂一点。

对以下内容的回复：

作者 lithbitren 2020-05-23 14:55

追问一下大佬，为啥写结构体需要标记泛型生命周期，直接用函数则不用强制标记呢。。

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        dfs(
            &mut preorder.iter(),
            &inorder.iter().enumerate().map(|(i, &j)| (j, i)).collect(),
            0, inorder.len()
        )
    }
}

use std::slice::Iter;
use std::collections::HashMap;
fn dfs(p: &mut Iter<'_, i32>, d: &HashMap<i32, usize>, i: usize, j: usize) -> Option<Rc<RefCell<TreeNode>>> {
    if i < j {
        let mut t = TreeNode::new(*p.next().unwrap());
        t.left = dfs(p, d, i, d[&t.val]);
        t.right = dfs(p, d, d[&t.val] + 1, j);
        return Some(Rc::new(RefCell::new(t)))
    }
    None
}

对以下内容的回复：

作者 lithbitren 2020-05-22 18:14

发现用into_iter就不用生命周期标记了。。

不过不知道差别的在哪。。

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Data {
            p: preorder.into_iter(),
            d: inorder.iter().enumerate().map(|(i, &j)| (j, i)).collect()
        }.f(0, inorder.len())
    }
}

struct Data {
    p: std::vec::IntoIter<i32>,
    d: std::collections::HashMap<i32, usize>
}

impl Data {
    fn f(&mut self, i: usize, j: usize) -> Option<Rc<RefCell<TreeNode>>> {
        if i < j {
            let mut t = TreeNode::new(self.p.next().unwrap());
            t.left = self.f(i, self.d[&t.val]);
            t.right = self.f(self.d[&t.val] + 1, j);
            return Some(Rc::new(RefCell::new(t)))
        }
        None
    }
}

作者 lithbitren 2020-05-22 17:00

谢谢大佬指点，对对就是这个意思。

对以下内容的回复：

xjkdev 2020-05-22 16:47

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn build_tree(preorder: Vec<i32>, inorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
        Data {
            i: 0,
            // p: preorder,
            p: preorder.iter(), //把迭代存进结构体
            d: inorder.iter().enumerate().map(|(i, &j)| (j, i)).collect()
        }.f(0, inorder.len())
    }
}

struct Data<'a> { // 生命周期要泛型
    i: usize,
    // p: Vec<i32>,
    p: std::slice::Iter<'a, i32>, //这里的生命周期不知道咋标，在struct和impl上标来标去要不编译不通过，要不说生命周期不够长。。
    d: std::collections::HashMap<i32, usize>
}

impl<'a> Data<'a>{ // impl也要泛型
    fn f(&mut self, i: usize, j: usize) -> Option<Rc<RefCell<TreeNode>>> {
        if i < j {
            // let mut t = TreeNode::new(self.p[self.i]);
            let mut t = TreeNode::new(*self.p.next().unwrap()); // 这里要解引用
            self.i += 1;
            t.left = self.f(i, self.d[&t.val]);
            t.right = self.f(self.d[&t.val] + 1, j);
            return Some(Rc::new(RefCell::new(t)))
        } 
        None
    }
}

1 共 6 条评论, 1 页