目錄

題目

解法一：遞歸

解法二：迭代

解法三：Morris遍歷

---

題目

解法一：遞歸

class Solution
{
private:void traverse(TreeNode* root, vector<int>& inorder){if (!root)return;traverse(root->left, inorder);inorder.push_back(root->val);traverse(root->right, inorder);}public:vector<int> inorderTraversal(TreeNode* root){vector<int> inorder;traverse(root, inorder);return inorder;}
};

解法二：迭代

class Solution
{
private:void traverse(TreeNode* root, stack<TreeNode*>& s,vector<int>& inorder){while (!s.empty() || root){while (root){s.push(root);root = root->left;}root = s.top();s.pop();inorder.push_back(root->val);root = root->right;}}public:vector<int> inorderTraversal(TreeNode* root){vector<int> inorder;stack<TreeNode*> s;traverse(root, s, inorder);return inorder;}
};

解法三：Morris遍歷

class Solution
{
private:void traverse(TreeNode* root, vector<int>& inorder){while (root){if (root->left){   TreeNode* node {root->left};while (node->right && node->right != root)node = node->right;if (!node->right){node->right = root;root = root->left;}else{node->right = nullptr;inorder.push_back(root->val);root = root->right;}}else{inorder.push_back(root->val);root = root->right;}}}public:vector<int> inorderTraversal(TreeNode* root){vector<int> inorder;traverse(root, inorder);return inorder;}
};