leetcode Remove Duplicates from Sorted Array II

gistfile1.cpp

递归代码：
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n <= 1) return n;//如果是空的或者只有一个元素，直接返回就行。
        int length = 1;//初始化总长度为1；
        int cnt = 1,i,j;//单个元素计数，初始化为1；
        for(i = 1,j = 1; j < n; j++){//从第二个元素开始比较；i作为指示某元素应该放的位置，j作为遍历到的元素的位置；
            if(A[j] == A[j-1]){//如果和前一个元素相同。用j指示。
                if(cnt >= 2) continue;//如果单个元素个数已经大于或者等于2，则跳过。
                else {//否则，元素个数还不到2
                    A[i] = A[j];//将遍历到的元素j放到应该放的位置i上。
                    i++;//i指示符前进一位
                    cnt++;//计数器加1
                    length++;
                   
                }
            }
            else {//如果和前一个元素值不同。
                A[i] = A[j];//表示遇到新的元素，移动到位置i;
                i++;
                cnt = 1;//新元素个数置为1；
                length++;
            }
        }
         return length;
    }
};

非递归代码：使用stack
class Solution {
public:
    void pre(TreeNode* root, vector<int> &vec){
        if(root == NULL) return;
        stack<TreeNode*> st;
        st.push(root);
        TreeNode *cur = root;                 //根先放进去
        while(!st.empty()){                   //如果栈不空。
            cur = st.top();                   //cur指向最上值。
            vec.push_back(cur->val);          //当前值放入vec;
            while(cur->left){                 //如果有左子树
                cur = cur->left;              //当前指针指向左子树
                st.push(cur);                 //节点放入栈中。
                vec.push_back(cur->val);      //值放入vector中
            }
            cur= st.top();
            st.pop();                         //如果没有左子树了，则指向最上面一个节点，并将其弹出；
            
            while(!st.empty() || cur->right){ //不空或者右子树存在。
                cur = cur->right;
                if(cur){
                    st.push(cur);
                    cur =  cur->right;
                    break;                    //只放进一个right
                }
                else{
                    cur = st.top();
                    st.pop();
                }
            }
            //st.pop();
        }
    }
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> vec;
        pre(root,vec);
        return vec;
    }
};