（含morris遍历）代码随想录 Leetcode144/94/145 二叉树的前/中/后序遍历

本文主要是介绍（含morris遍历）代码随想录 Leetcode144/94/145 二叉树的前/中/后序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

前：

中：

后：

代码（首刷自解 2024年1月24日）：

//前序遍历，递归
class Solution {
public:void funcOfRecursion(TreeNode* cur, vector<int>& vec) {if (cur == nullptr) return;vec.emplace_back(cur->val);funcOfRecursion(cur->left,vec);funcOfRecursion(cur->right,vec);}vector<int> preorderTraversal(TreeNode* root) {vector<int> vec = {};if (root == nullptr) return vec;funcOfRecursion(root,vec);return vec; }
};

//中序遍历，递归
class Solution {
public:void funcOfRecursion(TreeNode* cur,vector<int>& vec) {if(cur == nullptr) return;funcOfRecursion(cur->left,vec);vec.emplace_back(cur->val);funcOfRecursion(cur->right,vec);}vector<int> inorderTraversal(TreeNode* root) {vector<int> vec = {};if(root == nullptr) return vec;funcOfRecursion(root,vec);return vec;}
};

//后序遍历，递归
class Solution {
public:void funcOfRecursion(TreeNode* cur, vector<int>& vec) {if(cur == nullptr) return;funcOfRecursion(cur->left,vec);funcOfRecursion(cur->right,vec);vec.emplace_back(cur->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> vec = {};if(root == nullptr) return vec;funcOfRecursion(root,vec);return vec;}
};

//前序遍历，迭代
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res = {};if(root == nullptr) return res;stack<TreeNode*> st;TreeNode* cur = root;st.push(cur);while (!st.empty()) {TreeNode* node = st.top();st.pop();res.emplace_back(node->val);if(node->right) st.push(node->right);if(node->left) st.push(node->left);}return res;}
};

//中序遍历，迭代
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res = {};if(root == nullptr) return res;stack<TreeNode*> st;TreeNode* cur = root;while (!st.empty() || cur != NULL) {if (cur != nullptr) {st.push(cur);cur = cur -> left;} else {cur = st.top();res.emplace_back(cur->val);st.pop();cur = cur -> right;}}return res;}
};

//后序遍历 迭代
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res = {};if(root == nullptr) return res;stack<TreeNode*> st;TreeNode* cur = root;st.push(cur);while (!st.empty()) {TreeNode* node = st.top();st.pop();res.emplace_back(node->val);if(node->left) st.push(node->left);if(node->right) st.push(node->right);}reverse(res.begin(),res.end());return res;}
};

代码（二刷自解 2024年1月24日 morris遍历）：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res = {};if(root == nullptr) return res;TreeNode* cur = root;while (cur != nullptr) {if (cur->left) {TreeNode* predessor = cur->left;while (predessor->right && predessor->right != cur) {predessor = predessor->right;}if (predessor->right == cur) {predessor->right = nullptr;cur = cur->right;} else {res.emplace_back(cur->val);predessor->right = cur;cur = cur->left;}} else {res.emplace_back(cur->val);cur = cur->right;}}return res;}
};

morris前序遍历，时间复杂度O(n），空间复杂度O(1)；

设当前节点为cur

while (cur!=nullptr) {

if(cur有左孩子）{

if(cur的前驱右孩子是x) 前驱右孩子设为null，cur = cur右孩子；

if(cur的前驱右孩子为空) cur加入结果数组，前驱右孩子设为cur，cur=cur左孩子；

}

else if(cur没有左孩子){

cur加入结果数组；

cur = cur ->right;

}

}