Steven's Blog

Appearance

On this page

每天一道Rust-LeetCode(2019-08-10) ​

坚持每天一道题,刷题学习Rust.

题目描述 ​

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解题过程 ​

rust
use crate::share::TreeNode;
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    pub fn inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let mut v = Vec::new();
        Solution::inorder_internal(root, &mut v);
        v
    }
    fn inorder_internal(root: Option<Rc<RefCell<TreeNode>>>, v: &mut Vec<i32>) {
        if let Some(root) = root {
            Solution::inorder_internal(root.borrow().left.clone(), v);
            v.push(root.borrow().val);
            Solution::inorder_internal(root.borrow().right.clone(), v);
        }
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::build_tree;
    use crate::share::NULL;
    #[test]
    fn test_generate() {
        let t = build_tree(&vec![1, NULL, 2, NULL, NULL, 3]);
        println!("t={:?}", t);
        assert_eq!(Solution::inorder_traversal(t), vec![1, 3, 2]);
    }
}

一点感悟 ​

最开始的版本是这样的, 展示出来,主要是为了说明自己犯的一个低级错误.

rust
fn inorder_internal(root: Option<Rc<RefCell<TreeNode>>>, v: &mut Vec<i32>) {
        if root.is_none() {
            return;
        }
        let root = root.unwrap();
        match &root.borrow().left {
            None => {
                v.push(root.borrow().val);
                Solution::inorder_internal(root.borrow().right.clone(), v)
            }
            Some(ref r) => {
                Solution::inorder_internal(r.borrow().left.clone(), v);
                v.push(r.borrow().val);
                Solution::inorder_internal(r.borrow().right.clone(), v);
            }
        } ---------;-----
    }

题目本身非常简单,中间因为使用match进行匹配,希望减少不必要的递归,因为最后一句话没加分号,导致编译器总是提示borrowed value does not live long enough. 百思不得其解,最后加了分号才算解决.

其他 ​

欢迎关注我的github,本项目文章所有代码都可以找到.