173. 二叉搜索树迭代器

每天一道Rust-LeetCode(2019-11-14)

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

题目描述

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例:

BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false

提示:

next() 和 hasNext() 操作的时间复杂度是 O(1),并使用 O(h) 内存,其中 h 是树的高度。
你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 中至少存在一个下一个最小的数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/binary-search-tree-iterator
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

O(1)复杂度的思路:

  1. 使用map来保存数据 key到映射value以及双向链表中的元素
  2. get 查询,如果查询得到,从双向链表中移除并添加到尾部
  3. put 如果满了,则移除双向链表首部元素,同时插入map,添加到尾部
    手工模拟双向链表.
    双向链表操作直接借鉴自标准库

    解题过程

use crate::share::TreeNode;
use std::cell::RefCell;
use std::rc::Rc;

struct BSTIterator {
    path: Vec<Rc<RefCell<TreeNode>>>, //保存当前路径
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl BSTIterator {
    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        let mut bst = BSTIterator { path: Vec::new() };
        bst.push_left(root);
        bst
    }
    fn push_left(&mut self, root: Option<Rc<RefCell<TreeNode>>>) {
        if root.is_none() {
            return;
        }
        let r = root.unwrap();
        self.path.push(r.clone());
        self.push_left(r.borrow().left.clone());
    }
    /** @return the next smallest number */
    fn next(&mut self) -> i32 {
        let l = self.path.pop().unwrap();
        let val = l.borrow().val;
        //左节点已经处理过了,右节点需要处理
        let r = l.borrow().right.clone();
        self.push_left(r);
        val
    }

    /** @return whether we have a next smallest number */
    fn has_next(&self) -> bool {
        self.path.len() != 0
    }
}

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

    #[test]
    fn test_lru() {
        let t = build_tree_ignore_parent(&vec![7, 3, 15, null, null, 9, 20]);
        let mut bst = BSTIterator::new(t);
        assert_eq!(bst.next(), 3);
        assert_eq!(bst.has_next(), true);
        assert_eq!(bst.next(), 7);
        assert_eq!(bst.has_next(), true);
        assert_eq!(bst.next(), 9);
        assert_eq!(bst.has_next(), true);
        assert_eq!(bst.next(), 15);
        assert_eq!(bst.has_next(), true);
        assert_eq!(bst.next(), 20);
        assert_eq!(bst.has_next(), false);
    }
}

一点感悟

其他

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