/*
中序遍历四种方式
思路1：递归
思路2：普通迭代（只有左子树入栈）
一直走到最左子节点，经过的节点全都入栈
取出栈顶元素，遍历右子树
具体流程：
一直走到最左子节点（保证当前节点的左子树优先被处理）
取出栈顶 （左子树先入栈，再取栈顶节点）
处理当前节点
遍历右子树 （右子节点不入栈，只有左子节点入栈）
(不考虑右节点空不空，否则会导致root被pop()后下一轮再次被装入栈，导致无限循环)
思路3：通用迭代
标记 = 0，表示还没遍历该节点的左子树；
标记 = 1，表示已经遍历完左子树，但还没遍历右子树；
标记 = 2，表示已经遍历完右子树；
取栈顶节点（只top(), 不pop()）
标记 = 0，则将该节点的标记改成1，然后将其左子节点压入栈中；
标记 = 1，则说明左子树已经遍历完，处理当前节点，然后将该节点的标记改成2，并将右子节点压入栈中；
标记 = 2，则说明以该节点为根的子树已经遍历完，直接从栈中弹出即可；
思路4：Morris-traversal
当前节点无左子节点
处理当前节点
遍历右子树
当前节点有左子节点
找到前驱节点pre（左子树的最右子节点，中序遍历的前驱节点）
pre->right为null，说明从父节点转移过来，未遍历左子节点
pre->right = root
遍历左子树
pre->right为root，说明从子孙节点转移过来，已遍历左子节点
pre->right = null
处理当前节点
遍历右子树
分析：左子树肯定不为空（进行了提前判定）；右子树如果为空，则是其他节点的前驱（或者是中序遍历最后一个节点）
*/
思路2 普通迭代
中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while(root || stk.size()) {
while (root) { // 一直走到最左子节点
stk.push(root);
root = root->left;
}
root = stk.top(); stk.pop();
res.push_back(root->val);
root = root->right; // 遍历右子树，不考虑root->right是否空
}
return res;
}
};
前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root || stk.size()) {
while (root) { // 走到最左子节点，全部入栈
res.push_back(root->val); // 处理当前节点
stk.push(root);
root = root->left;
}
root = stk.top(); stk.pop();
root = root->right; // 遍历右子树，不考虑root->right是否空
}
return res;
}
};
后序遍历（前序遍历逆运用）
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
// 根右左遍历
while (root || stk.size()) {
while (root) { // 右子树全部入栈
res.push_back(root->val); // 处理当前节点
stk.push(root);
root = root->right;
}
root = stk.top(); stk.pop();
root = root->left; // 遍历左子树，不考虑root->left是否空
}
reverse(res.begin(), res.end()); // 根右左 -> 左右根
return res;
}
};
思路3 通用迭代
中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> nums;
stack<pair<TreeNode*, int>> stk;
stk.push(make_pair(root, 0));
while(!stk.empty()) {
pair<TreeNode*, int> &ns = stk.top(); // node&state
if (!ns.first) { // 节点为空
stk.pop();
continue;
}
if (ns.second == 0) { // 节点标识为0
ns.second = 1;
stk.push(make_pair(ns.first->left, 0));
}
else if (ns.second == 1) { // 节点标识为1
ns.second = 2; // 改为stk.pop()也行，不需要使用标识2
nums.push_back(ns.first->val);
stk.push(make_pair(ns.first->right, 0));
}
else if (ns.second == 2) { // 节点标识为2
stk.pop();
}
}
return nums;
}
};
前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return {};
stack<TreeNode*> stk;
stk.push(root);
TreeNode* p = nullptr;
while(stk.size()) {
p = stk.top(); stk.pop();
res.push_back(p->val);
if (p->right) stk.push(p->right);
if (p->left) stk.push(p->left);
}
return res;
}
};
后序遍历
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<pair<TreeNode*, int>> stk;
stk.emplace(root, 0);
while (stk.size()) {
pair<TreeNode*, int> &ns = stk.top(); // node & state
if (ns.second == 0) {
if (ns.first->right)
stk.emplace(ns.first->right, 0);
if (ns.first->left)
stk.emplace(ns.first->left, 0);
ns.second = 2;
}
else if (ns.second == 2) {
res.push_back(ns.first->val);
stk.pop();
}
}
return res;
}
};
思路4 Morris遍历
中序遍历
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
while(root) {
// 无左子树
if (!root->left) {
res.push_back(root->val); //处理当前节点
root = root->right; //遍历右子树
}
// 有左子树
else {
// 找到左子树的最右子节点，中序遍历的前驱节点
auto p = root->left;
while (p->right && p->right != root) p = p->right;
// p->right 为空
if (!p->right) {
p->right = root;
root = root->left; //遍历左子树
}
// p->right 非空
else {
p->right = nullptr;
res.push_back(root->val); //处理当前节点
root = root->right; //遍历右子树
}
}
}
return res;
}
};
前序遍历
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
while (root) {
if (!root->left) {
res.push_back(root->val);
root = root->right;
}
else {
// 找到左子树的最右子节点，中序遍历的前驱节点
TreeNode *pre = root->left;
while (pre->right && pre->right != root) pre = pre->right;
// 通过前驱判断左子树是否被遍历过
if (!pre->right) {
pre->right = root;
res.push_back(root->val);
root = root->left;
}
else {
pre->right = nullptr;
root = root->right;
}
}
}
return res;
}
};
后序遍历（前序遍历逆运用）
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
// 根右左遍历
while (root) {
if (!root->right) {
res.push_back(root->val);
root = root->left;
}
else {
// 找到右子树的最左子节点，中序遍历的后继节点
TreeNode *post = root->right;
while (post->left && post->left != root) post = post->left;
// 判断右子树有没有被遍历过
if (!post->left) {
post->left = root;
res.push_back(root->val);
root = root->right;
}
else {
post->left = nullptr;
root = root->left;
}
}
}
reverse(res.begin(), res.end()); // 根右左 -> 左右根
return res;
}
};
