86. Binary Search Tree Iterator(

2019-06-21  本文已影响0人  鸭蛋蛋_8441

Description

Design an iterator over a binary search tree with the following rules:

Elements are visited in ascending order (i.e. an in-order traversal)

next() and hasNext() queries run in O(1) time in average.

Example

Example 1

Input:  {10,1,11,#,6,#,12}

Output:  [1, 6, 10, 11, 12]

Explanation:

The BST is look like this:

  10

  /\

1 11

  \  \

  6  12

You can return the inorder traversal of a BST [1, 6, 10, 11, 12]

Example 2

Input: {2,1,3}

Output: [1,2,3]

Explanation:

The BST is look like this:

  2

/ \

1  3

You can return the inorder traversal of a BST tree [1,2,3]

Challenge

Extra memory usage O(h), h is the height of the tree.

Super Star: Extra memory usage O(1)

思路:

该 Iterator 算法即 non-recursion 的 inorder traversal,不仅仅适用于 BST,任何 Binary Tree 都可以

• stack 中保存一路走到当前节点的所有节点

• stack的栈顶 一直存储 iterator 指向的当前节点

• hasNext() 只需要判断 stack 是否为空

• next() 只需要返回 stack 的栈顶值,并将 iterator 挪到下一个点,对 stack 进行相应的变化

挪到下一个点的算法如下:

• 如果当前点存在右子树,那么就是右子树中“一路向左”最左边的那个点

• 如果当前点不存在右子树,则是走到当前点的路径中,第一个左拐的点(这个判断十分重要)

代码:

上一篇 下一篇

猜你喜欢

热点阅读