题解 | 二叉树的中序遍历

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    /*void ioTraversal(TreeNode* root,vector<int> &res)
    {
        if(root!=nullptr)
        {
            ioTraversal(root->left,res);
            res.push_back(root->val);
            ioTraversal(root->right,res);

        }
        else {
           return;
        }
    }*/
    /*vector<int> inorderTraversal(TreeNode* root) {
        // write code here
       vector<int> res;
       stack<TreeNode*> s;
       if(root==nullptr)
       {
            return res;
       }
       TreeNode* cur = root;
       while(cur!=nullptr||!s.empty())
       {
        while(cur!=nullptr)
        {
            s.push(cur);
            cur=cur->left;
        }
        cur=s.top();
        s.pop();
        res.push_back(cur->val);
        cur=cur->right;
       }
       return res;
      */
      vector<int> inorderTraversal(TreeNode* root) {
        // write code here
       vector<int> res;
       if(root==nullptr)
       {
            return res;
       }
       TreeNode* cur = root;
       while(cur!=nullptr)
       {
        if(cur->left==nullptr)
        {
           res.push_back(cur->val);
           cur=cur->right;
        }
        else {
            TreeNode* temp=cur->left;
            while(temp->right!=nullptr&&temp->right!=cur)
            {
                temp=temp->right;
            }
            if(temp->right==nullptr)
            {
                temp->right=cur;
                cur=cur->left;
            }
            else
            {
                res.push_back(cur->val);
                temp->right=nullptr;
                cur=cur->right;
            }
        }
       }
          return res;
    
    }
};