leetcode<144. 二叉树的前序遍历><94. 二叉树的中序遍历>非递归实现

vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;            //使用栈暂存走过的左节点
        vector<int> v;                 //vector存储节点数据
        TreeNode* cur = root;
        if(root == nullptr) return v;  //空树返回空的vector
        while(cur||s.size())           //只要当前节点或栈不为空则需要继续走
        {
            while(cur)                 //直到当前节点为空
            {
                v.push_back(cur->val); //记录当前节点
                s.push(cur);           //左节点都入栈
                cur = cur->left;       //继续访问左节点
            }
            cur = s.top()->right;      //回溯访问栈顶元素的右子树
            s.pop();                   //出栈
        }
        return v;
    }

vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s; 
        vector<int> v;
        if(root == nullptr) return v;
        TreeNode* cur = root;
        while(cur||s.size())
        {
            while(cur)            //直到空才结束
            {
                s.push(cur);      //左节点入栈
                cur = cur->left;  //继续访问左节点
            }
            cur = s.top();        //回溯上一个左节点
            s.pop();
            v.push_back(cur->val); //写入当前节点
            cur = cur->right;     //访问当前节点右子树
        } 
        return v;
    }