My Solution in C, using pointer to pointer

• ``````/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     struct TreeNode *left;
*     struct TreeNode *right;
* };
*/
struct BSTIterator {
struct TreeNode **stack;
int top;
};

struct BSTIterator *bstIteratorCreate(struct TreeNode *root) {
if(root == NULL)
return NULL;

struct BSTIterator *iter;
struct TreeNode **stackTmp;
struct TreeNode *p;

iter->stack = (struct TreeNode **)malloc(sizeof(struct TreeNode *)*6000);
iter->top = -1;
stackTmp = iter->stack;

// 左节点全部进栈
p = root;

while(p != NULL)
{
iter->top ++;
stackTmp[iter->top] = p;
p = p->left;
}

return iter;
}

/** @return whether we have a next smallest number */
bool bstIteratorHasNext(struct BSTIterator *iter) {
if(iter == NULL)
return false;

if(iter->top >= 0)
return true;
else
return false;
}

/** @return the next smallest number */
int bstIteratorNext(struct BSTIterator *iter) {

struct TreeNode **stackTmp;
stackTmp = iter->stack;
struct TreeNode *p;

// 出栈一个元素
int top = iter->top;
int ret;
p = stackTmp[top];
iter->top --;
ret = p->val;

p = p->right;
while(p != NULL)
{
iter->top ++;
stackTmp[iter->top] = p;
p = p->left;
}

return ret;
}

/** Deallocates memory previously allocated for the iterator */
void bstIteratorFree(struct BSTIterator *iter) {
if(iter != NULL)
{
struct TreeNode *stack = (iter->stack);
free(stack);
}
}

/**
* Your BSTIterator will be called like this:
* struct BSTIterator *i = bstIteratorCreate(root);
* while (bstIteratorHasNext(i)) printf("%d\n", bstIteratorNext(i));
* bstIteratorFree(i);
*/``````

• I dont think its acceptable. you allocage 6000 items which is a "magic number" in development. This is the first place where I would look for bugs. you also have O(n) memory complexity. I would hate my job if someone asks me to support this code and not be able to rewrite it.

Try to simplify or use existing solutions. Take a look on common iterative traversing and utilize that for current problem.
Good luck.

• The problem is there is no existing Stack data structure in C, we have to realize a stack by using array. So I have to use a "magic number". In C++, you can use STL, such as "stack", "dequeue", this container will automatically expand its size. But for C programer, it is luxurious.

Of course, I can use STL to realize the solution in C++. You can see it below. But I think this two codes are same in nature.

As for memory complexity, I think the memory complexity is O(h).

• ``````/**
* Definition for binary tree
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class BSTIterator {
public:
stack<TreeNode*> stk;
int nextmin;
BSTIterator(TreeNode *root) {
while(root)
{
stk.push(root);
root = root->left;
}
}

/** @return whether we have a next smallest number */
bool hasNext() {
if(!stk.empty())
{
TreeNode* top = stk.top();
stk.pop();
nextmin = top->val;
TreeNode* cur = top->right;
if(cur)
{
stk.push(cur);
cur = cur->left;
while(cur)
{
stk.push(cur);
cur = cur->left;
}
}
return true;
}
else
return false;
}

/** @return the next smallest number */
int next() {
return nextmin;
}
};

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

• in C you still have pointers. so you can make list your own with push_back, pop_back and size. not a big deal. But my point was that you should allocate only what you need.

• It comes with the RunTime error !
Somebody can explain why?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.