详细思路

cur是当前需要判断，只有当前想要才push，只有想使用值才pop，二叉树必画六星图

 

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode*cur=root;
        while(cur||!stk.empty()){
            while(cur){
                stk.push(cur);
                cur=cur->left;
            }
            TreeNode*tmp=stk.top();
            stk.pop();
            ans.push_back(tmp->val);
            cur=cur->right;
        }
    }
};

详细思路 莫里斯遍历，下降期处理好cur的左子树pre，然后上升期遍历左子树， 当上升期结束正好下一个节点是子树cur->right 这样循环，一个循环既包括下降处理pre又包括上升遍历

 

 

 

 

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        TreeNode *pre,*cur=root;
        while (cur) {
            if (cur->left) {
                //找到pre
                //如果pre->right不存在说明是下降期，需要连接pre并去下一个节点
                //如果pre->right为cur说明是上升期，需要更新答案断开pre去下一个节点，当上升期结束正好下一个节点就是cur->next
                pre = cur->left;
                while (pre->right&&pre->right != cur)pre = pre->right;
                if (!pre->right) {
                    pre->right = cur;
                    cur = cur->left;
                }
                else if(pre->right==cur){
                    ans.push_back(cur->val);
                    pre->right = nullptr;
                    cur = cur->right;
                }
            }
            //如果没有左孩子，说明需要更新答案通过pre上升
            else if(!cur->left){
                ans.push_back(cur->val);
                cur = cur->right;
            }
        }
        return ans;
    }
};