Description

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.
NOTE: `next()` and `hasNext()` should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Solution

In a binary search tree, in-order traversal retrieves data in sorted order. In general we traverse the tree from left to right, thus we’ll get a sequence in ascending order. With this knowledge in mind, we can easily implement an iterator over a BST.

In-order traversal review

```iterativeInorder(node)
s ← empty stack
while (not s.isEmpty() or node ≠ null)
if (node ≠ null)
s.push(node)
node ← node.left
else
node ← s.pop()
visit(node)
node ← node.right
```

We cannot directly apply above iterative in-order traversal to the solution, because we are required to use O(h) memory. We can easily overcome this by dividing the total process into two stages. In first stage, we put elements into a stack, the number of elements is O(h). In second stage, we retrieve element.

C++ implementation

```/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
private:
stack<TreeNode*> st;

public:
BSTIterator(TreeNode *root) {
auto p = root;
while (root) {
st.push(root);
root = root->left;
}
}

/** @return whether we have a next smallest number */
bool hasNext() {
return !st.empty();
}

/** @return the next smallest number */
int next() {
auto n = st.top();
st.pop();
auto p = n->right;
while (p) {
st.push(p);
p = p->left;
}
return n->val;
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
```

In our constructor of `BSTIterator`, we continue to push element of left node into the stack until left node is null. After this, there are O(h) elements in the stack. `hasNext()` just checks if the stack is empty, which is O(1). In `next()`, we remove an element from the stack and deal with its right subtree until we push the next smallest element into the stack, the push operations don’t matter, the number of elements in stack remains O(h). (Todo: time complexity analysis)

iTerm 配置

```xterm-256color-italic|xterm with 256 colors and italic,
sitm=\E[3m, ritm=\E[23m,
use=xterm-256color,
```

```tic -x xterm-256color-italic.terminfo
```

Vim 配置

`~/.vimrc`中添加如下配置项：

```if (has("termguicolors"))
set termguicolors
endif
let g:material_theme_style = 'default'
let g:material_terminal_italics = 1
set background=dark
colorscheme material
```

问题

```export TERM=xterm-256color
alias ls='ls --color=auto'
```

效果 购买一台VPS

```apt-get update
apt-install python-pip
```

```ssserver -c /etc/shadowsocks.json -d start
```

```{
"server": "server_ip",
"server_port": server_port,