# Binary Search Tree Iterator

Mar 31, 2020

## 递归

class BSTIterator {
public:
vector<int> vec;
int index;
BSTIterator(TreeNode* root) {
index = 0;
inorderTraversal(root);
}

void inorderTraversal(TreeNode *root) {
if (root) {
inorderTraversal(root->left);
vec.push_back(root->val);
inorderTraversal(root->right);
}
}

/** @return the next smallest number */
int next() {
return vec[index++];
}

/** @return whether we have a next smallest number */
bool hasNext() {
return index != vec.size();
}
};


## 基于栈进行迭代。

1. 不断地把先左节点移动，并把节点压入栈中（以下简称 step 1)。
2. 弹出栈顶节点，并输出，然后先右节点方向移动（以下简称 step 2)。

class BSTIterator {
public:
stack<TreeNode *> st;
BSTIterator(TreeNode* root) {
pushleft(root);
}

void pushleft(TreeNode *root) {
while(root) {
st.push(root);
root = root->left;
}
}

/** @return the next smallest number */
int next() {
auto root = st.top(); st.pop();
pushleft(root->right);
return root->val;
}

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


## 莫里斯遍历

TreeNode *GetRightLeaf(TreeNode *root, TreeNode *end) {
while(root->right && root->right != end) root = root->right;
return root;
}

void inorderTraversal(TreeNode* root) {
while(root) {
if (root->left) {
TreeNode *p = GetRightLeaf(root->left, root);
if (p->right == root) {
p->right = nullptr;
cout << root->val << endl;
root = root->right;
} else {
p->right = root;
root = root->left;
}
} else {
cout << root->val << endl;
root = root->right;
}
}
}


class BSTIterator {
public:
TreeNode *root;
TreeNode *GetRightLeaf(TreeNode *root, TreeNode *end) {
while(root->right && root->right != end) root = root->right;
return root;
}

BSTIterator(TreeNode* _root):root(_root) {

}

/** @return the next smallest number */
int next() {
int res = -1;
while(root) {
if (root->left) {
TreeNode *p = GetRightLeaf(root->left, root);
if (p->right == root) {
p->right = nullptr;
// cout << root->val << endl;
res = root->val;
root = root->right;
break;
} else {
p->right = root;
root = root->left;
}
} else {
// cout << root->val << endl;
res = root->val;
root = root->right;
break;
}
}
return res;
}

/** @return whether we have a next smallest number */
bool hasNext() {
return root != nullptr;
}
};


LeetCodeLeetCodeStackTreeDesign

677. Map Sum Pairs

Evaluate Reverse Polish Notation