Tree的遍历

今天一个朋友来帮我mock interview. 感觉自信心又收到了打击。看来我真的是自我认知不够正确外加过于乐观不知轻重。好吧，让我在打击中继续前行!

今天就来总结一下朋友问我的问题。
How to write a TreeIterator?

具体分析：
1. TreeIterator, 通过名字就该知道，这个题目是考察 tree的iterative traversal. 然后发现自己给出的答案的确开始没有注意到这点，这种感觉就像明明告诉你了，前方左转，我却依然右转一样。哎。。

2. Problem Definition.
问清楚题目的要求，input, output, 要handle的情景。
interface,  precondition, 树的traversal的方式.

3. 问题归一化。
在c++ stl里面有iterator
对于 iterator, 可能包括的函数有，

• a. construct Iterator
• b. next -> return value. Node？or value? error handling
• c. hasNext -> return bool
• d. single direction of bi-direction

4. Tree的traversal
分为三种，pre-order, in-order and post-order.
Pre-order: 
recursive

void preOrder(TreeNode * root)
{
    if (root == nullptr)
    {
        return;
    }
    cout << root->val;
    preOrder(root->left);
    preOrder(root->right);
}

iterative
stack<TreeNode*> m_nodeStack;
只要stack不是empty的时候，就可以继续，直到stack is empty循环结束。

void preOrder2(TreeNode *root)
{
    stack<TreeNode*> node_stack;
    node_stack.push(root);
    
    while(!node_stack.empty())
    {
        auto top = node_stack.top();
        node_stack.pop();
        cout << top->val;
        
        if (top->right)
        {
            node_stack.push(top->right);
        }
        if (top->left)
        {
            node_stack.push(top->left);
        }
    }
}

in-order

void inOrder(TreeNode * root)
{
    if (root == nullptr)
    {
        return;
    }
    
    preOrder(root->left);
    cout << root->val;
    preOrder(root->right);
}

in-order iterative: 
idea:
function call in recursion behave like stack, when reaches recursion termination condition, we starts popping out last function call in stack and starts putting right side of node into stack, and etc.

stack<TreeNode*>
TreeNode* curr  :To remember last state of function call, to help us decide if we need pop out stack. 

if (curr == nullptr)
// we reach the termination condition of recursion call -> pop
after pop, start putting right child of node to stack.