//用栈来实现非递归解法
/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> preorderTraversal(TreeNode* root) {

        vector<int> res;

        if(root == NULL)

            return res;

        stack<TreeNode*> stack;

        stack.push(root);

        while(!stack.empty()){

            TreeNode* c = stack.top();

            stack.pop();

            res.push_back(c->val);

            if(c->right)

                stack.push(c->right);

            if(c->left)

                stack.push(c->left);

        }

        return res;

    }

};

//递归解法，注意res是全局的，要放在遍历函数外面
/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> res;

    vector<int> preorderTraversal(TreeNode* root) {

        if(root){

            res.push_back(root->val);

            preorderTraversal(root->left);

            preorderTraversal(root->right);

        }

        return res;

    }

};

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> inorderTraversal(TreeNode* root) {

        stack<TreeNode*> st;

        vector<int> res;

        if(root == NULL) return res;  //若根节点为空则返回空

        TreeNode* p = root;

        while(p || !st.empty()){

            while(p){

                //先将根节点入栈，再将它所有的左节点入栈

                st.push(p);

                p = p->left;

            }

            p = st.top();

            st.pop();

            res.push_back(p->val);

            p = p->right;

        }

        return res;

    }

};

//解法一
/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> postorderTraversal(TreeNode* root) {

        if(!root) return {};

        vector<int> res;

        stack<TreeNode*> s{{root}};

        while(!s.empty()){

            TreeNode* t = s.top();

            s.pop();

            res.insert(res.begin(), t->val);

            if(t->left) s.push(t->left);

            if(t->right) s.push(t->right);

        }

        return res;

    }

};

/**

 * Definition for a binary tree node.

 * struct TreeNode {

 *     int val;

 *     TreeNode *left;

 *     TreeNode *right;

 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}

 * };

 */

class Solution {

public:

    vector<int> postorderTraversal(TreeNode* root) {

        if(!root) return {};

        vector<int> res;

        stack<TreeNode*> s{{root}};

        TreeNode* head = root;   //head初始化

        while(!s.empty()){

            TreeNode* t = s.top();

            if((!t->left && !t->right) || t->left==head || t->right==head){

                //当t为叶子结点 或t的左结点或右结点为head，即已经入栈了

                res.push_back(t->val);

                s.pop();

                head = t;

            }

            else{

                if(t->right) s.push(t->right);

                if(t->left) s.push(t->left);

            }

        }

        return res;

    }

};

/**

 * // This is the interface that allows for creating nested lists.

 * // You should not implement it, or speculate about its implementation

 * class NestedInteger {

 *   public:

 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.

 *     bool isInteger() const;

 *

 *     // Return the single integer that this NestedInteger holds, if it holds a single integer

 *     // The result is undefined if this NestedInteger holds a nested list

 *     int getInteger() const;

 *

 *     // Return the nested list that this NestedInteger holds, if it holds a nested list

 *     // The result is undefined if this NestedInteger holds a single integer

 *     const vector<NestedInteger> &getList() const;

 * };

 */

class NestedIterator {

public:

    stack<NestedInteger> s;

    NestedIterator(vector<NestedInteger> &nestedList) {

        for(int i=nestedList.size()-; i>=; i--)

            //倒序插入 是为了弹出时是正序的

            s.push(nestedList[i]);

    }

    int next() {

        //返回下一项的值

        NestedInteger t = s.top();

        s.pop();

        return t.getInteger();  //获取对应整数

    }

    bool hasNext() {

        //若下一项有值，返回true

        while(!s.empty()){

            NestedInteger t = s.top();

            if(t.isInteger())

                return true;   //若下一个数是单个整数，返回true

            s.pop();

            //若下一个数是一个列表,使用getList()得到列表的每个整数倒序插入到栈中

            for(int i=t.getList().size()-; i>=; i--)

                s.push(t.getList()[i]);

        }

        return false;

    }

};

/**

 * Your NestedIterator object will be instantiated and called as such:

 * NestedIterator i(nestedList);

 * while (i.hasNext()) cout << i.next();

 */