文件名称:
README.md
所在目录:
教材与参考资料 / 程序设计类 / 数据结构＆算法 / 算法 / 面试与力扣题目详解 / Leetcode题目和解答 / java-leetcode / binary-search-tree-iterator
文件大小:
1.43 KB
下载地址:
文本预览:
## [Yielding](http://en.wikipedia.org/wiki/Generator_(computer_programming)) and [Binary Tree Inorder Traversal](../binary-tree-inorder-traversal)
In the problem [Binary Tree Inorder Traversal](../binary-tree-inorder-traversal),
we solved it by simlating the function call.
Only a bit different this time,
when the caller calls `next()`:
1. just execute to next value returns
1. save the stack and next address (state)
1. yield the node value and return control to caller
actions above is the `while` body part in the [Binary Tree Inorder Traversal](../binary-tree-inorder-traversal).
### Edge cases in `hasNext()`
like [Binary Tree Inorder Traversal](../binary-tree-inorder-traversal),
when the stack is empty, there are no more nodes.
However, if only one state left in the stack and the address of the state is `POST`,
we need some additional check.
`POST` state here means to deal with right node of current node (value already yeild to caller when `IN` step).
sometimes, the node does not have right child. we should return false when caller ask `hasNext()`.
## Why it is `O(h)` in space
the space here used in my solution is the `stack`.
only tree nodes with left child will consume a space in the `stack`.
because nodes without left child can be yield to caller directly.
Worst case
```
1
/
2
/
3
```
here we have to save `node 1` and `node 2` before we found `node 3`.
but the space used in stack will be no more than 3.
In the problem [Binary Tree Inorder Traversal](../binary-tree-inorder-traversal),
we solved it by simlating the function call.
Only a bit different this time,
when the caller calls `next()`:
1. just execute to next value returns
1. save the stack and next address (state)
1. yield the node value and return control to caller
actions above is the `while` body part in the [Binary Tree Inorder Traversal](../binary-tree-inorder-traversal).
### Edge cases in `hasNext()`
like [Binary Tree Inorder Traversal](../binary-tree-inorder-traversal),
when the stack is empty, there are no more nodes.
However, if only one state left in the stack and the address of the state is `POST`,
we need some additional check.
`POST` state here means to deal with right node of current node (value already yeild to caller when `IN` step).
sometimes, the node does not have right child. we should return false when caller ask `hasNext()`.
## Why it is `O(h)` in space
the space here used in my solution is the `stack`.
only tree nodes with left child will consume a space in the `stack`.
because nodes without left child can be yield to caller directly.
Worst case
```
1
/
2
/
3
```
here we have to save `node 1` and `node 2` before we found `node 3`.
but the space used in stack will be no more than 3.
点赞
回复
X