problem0173

package
v0.0.0-...-db5e768 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 25, 2019 License: MIT Imports: 1 Imported by: 0

README

173. Binary Search Tree Iterator

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

bst

Example:

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

Note:

  • next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
  • You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type BSTIterator

type BSTIterator struct {
	// contains filtered or unexported fields
}

BSTIterator is the iterator of BST

func Constructor

func Constructor(root *TreeNode) BSTIterator

Constructor returns a BST iterator

func (*BSTIterator) HasNext

func (it *BSTIterator) HasNext() bool

HasNext returns whether we have a next smallest number

func (*BSTIterator) Next

func (it *BSTIterator) Next() int

Next returns the next smallest number

type TreeNode

type TreeNode = kit.TreeNode

TreeNode is pre-defined...

Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL