核心思路是：把left节点指向parent。因为是中序遍历，而且使用深度搜索的方式，当搜索走到某个节点时，它的左节点整个子树的内容都已经遍历完成，不需要了。
class BSTIterator {
TreeNode *cur = new TreeNode(0);
TreeNode *parent = nullptr;
//找到子树的第一个节点，也就是最左边的节点，并且在遍历过程中翻转left指针指向parent
inline void findTreeFirst(){
auto left = cur->left;
cur->left = parent;
while (left) {
parent = cur;
cur = left;
left = cur->left;
cur->left = parent;
}
}
public:
BSTIterator(TreeNode * root) {
cur->right = root;
}
bool hasNext() {
if (cur->right) {
return true;
}
auto check = cur;
//看是父节点里是否还有一个是左孩子的，左孩子的父节点在中序遍历靠后，就还需要继续处理，否则结束
while (check->left && check->left->right == check) {
check = check->left; //实际是去到parent
}
return check->left != nullptr;
}
TreeNode * next() {
if (cur->right) {
parent = cur;
cur = cur->right;
findTreeFirst();
}else{
//cur是右孩子，就要一直向上追溯，知道父节点为空，或者找到cur是左孩子。因为右孩子的父节点在中序遍历里是靠前的，它已经遍历结束。
while (cur->left && cur->left->right == cur) {
cur = cur->left; //实际是去到parent
}
cur = cur->left;
}
return cur;
}
};
