记录下可以用的中序遍历方法

 

方法1：

vector
     
       InOrderTraverse(TreeNode * root) //中序遍历    {        vector
      
        ans;        TreeNode* p;        vector
       
         Stack;        Stack.push_back(root);        while(!Stack.empty())        {            while((p = Stack.back()) != NULL)                 Stack.push_back(p->left);            Stack.pop_back();            if(!Stack.empty())            {                p = Stack.back();                 Stack.pop_back();                ans.push_back(p->val);                Stack.push_back(p->right);            }        }        return ans;    }
       
      
     

方法2：

vector
     
       inorderTraversal(TreeNode *root) {        vector
      
        vector;        stack
       
         stack;        TreeNode *pCurrent = root;        while(!stack.empty() || pCurrent)        {            if(pCurrent)            {                stack.push(pCurrent);                pCurrent = pCurrent->left;            }            else            {                TreeNode *pNode = stack.top();                vector.push_back(pNode->val);                stack.pop();                pCurrent = pNode->right;            }        }        return vector;    }
       
      
     

 

我按照自己的思路写的，调了很多遍。关键是右子树弹出时候的逻辑混乱

vector
     
       inorderTraversal(TreeNode *root) {        vector
      
        ans;        vector
       
         v;        TreeNode * p;        if(root == NULL) return ans;        v.push_back(root);        while(!v.empty())        {            p = v.back();            while(p->left != NULL) //找到最左边的            {                v.push_back(p->left);                p = p->left;            }            ans.push_back(p->val); //压入数据            v.pop_back();            while(p->right == NULL) //右子树处理 如果当前的右子树是空的 那么需要弹出v中栈尾的数值            {                if(!v.empty())                {                    p = v.back();                    ans.push_back(p->val);                    v.pop_back();                }                else                {                    break;                }            }            if(p->right != NULL)            {                v.push_back(p->right);            }        }        return ans;    }
       
      
     

 

还有不需要栈的方法，利用了线索二叉树的概念，空间复杂度O(1)