https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

迭代遍历

由于二叉树结构本身就是递归的（每一个节点都是一个子树），所以递归写法好理解，写法也简洁

void traversal(TreeNode* node, vector<int>& vec) {
    if (!node) {
        return;
    }

    // 左
    traversal(node->left, vec);
    // 中
    vec.push_back(node->val);
    // 右
    traversal(node->right, vec);
}

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> ans;
    traversal(root, ans);
    return ans;
}

迭代遍历

由于中序遍历时，对节点的访问与操作不是在同一步中进行的，所以迭代遍历的写法与前序后序有所不同。

<aside> 💡

不断访问左孩子，直到没有左孩子时取出栈顶节点进行操作

</aside>

// 迭代遍历
vector<int> inorderTraversal(TreeNode* root) {
	vector<int> ans;
	stack<TreeNode*> st;
	TreeNode* cur = root;

	while (cur || !st.empty()) {
		// 节点非空时访问节点，但不对节点进行操作，
		// 而是不断将其压入栈并继续访问其左孩子
		while (cur) {
			st.push(cur);
			cur = cur->left;		// 左
		}
		// 直到左孩子为空节点时，才从栈中弹出节点进行操作
		cur = st.top();			// 中
		st.pop();
		ans.push_back(cur->val);
		cur = cur->right;		// 右
	}
	return ans;
}

迭代遍历——统一写法

<aside> 💡

boolen标记法思路：

1. 对节点进行访问时，先不进行操作，而是将节点展开为一个子树，将树中的节点以右-中-左的顺序压入栈。（前序与后序在这步改变一下入栈的顺序即可）
2. 使用一个空指针来标记已经被访问但还未被操作的节点（即上一步中的中节点）。之后遇到空指针就表示需要对栈中下一个元素进行操作了。 </aside>

// 迭代——统一写法
vector<int> inorderTraversal(TreeNode* root) {
		vector<int> ans;
		stack<TreeNode*> st;
		TreeNode* cur;
		if (root)
				st.push(root);
		while (!st.empty()) {
				cur = st.top();
				if (cur) {
						// 先将栈顶弹出
						st.pop();
		
						// 将栈顶节点扩展成一个子树，按右-中-左的顺序压入栈
						// 右
						if (cur->right)
								st.push(cur->right);
						// 中，中节点访问但还没操作，后面加入一个空指针作为标识
						st.push(cur);
						st.push(nullptr);
						// 左
						if (cur->left)
								st.push(cur->left);
				}
				// 碰到了标示符（空指针），说明此时该对节点进行操作了
				else {
						// 先将空指针弹出，再对栈顶元素进行操作
						st.pop();
						cur = st.top();
						ans.push_back(cur->val);
						// 最后将操作完成的栈顶元素弹出
						st.pop();
				}
		}
		return ans;
}