学步园

#include <iostream>
#include <stack>
using namespace std;

struct Node
{
    int value;
    Node *left;
    Node *right;
};

void  inorderTraverse(Node *root)
{
    if (NULL == root)
    {
        return;
    }
    
    //用p来记录最后弹出的节点
    Node *p = root;
    stack<Node*> buf;
    buf.push(root);
    while (!buf.empty())
    {
        Node *top = buf.top();
        if (top->left == NULL && top->right == NULL)
        {
            cout << top->value << " ";
            p = top;
            buf.pop();
        }
        else if (top->left != NULL &&  top->right == NULL)
        {
            if (p == top->left)
            {
                cout << top->value << " ";
                p = top;
                buf.pop();
            }
            else
            {
                buf.push(top->left);
            }
        }
        else if (top->left == NULL && top->right != NULL)
        {
            if (p == top->right)
            {
                p = top;
                buf.pop();
            }
            else
            {
                cout << top->value << " ";
                buf.push(top->right);
            }
        }
        else
        {
            if (p == top->left)
            {
                cout << top->value << " ";
                buf.push(top->right);
            }
            else if (p == top->right)
            {
                p = top;
                buf.pop();
            }
            else
            {
                buf.push(top->left);
            }
        }
    }
}