二叉树的统一迭代法

class TreeNode
{
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode():val(NULL),left(nullptr),right(nullptr){}
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) 
    {
        if(root != nullptr) sta.push(root);
        while(!sta.empty())
        {
            TreeNode *node = sta.top();
            if(node)
            {
                sta.pop();
                //是什么序遍历 就倒序push 需要注意的是 插入中间节点的时候要在后面插入一个空指针
                if(node->right) sta.push(node->right);
                sta.push(node);
                sta.push(nullptr);
                if(node->left) sta.push(node->left);
            }
            else
            {
                sta.pop();//弹出空指针
                node = sta.top();    // 重新取出栈中元素
                sta.pop();
                res.push_back(node->val); // 加入到结果集
            }
        }
        return res;
    }
private:
    stack<TreeNode*> sta;
    vector<int> res;
};