二叉树统一迭代写法

思路

前面说了，前序/后序和中序不能统一的原因是因为，访问和处理的时机不同，如果要做到同时处理，我们可以在要处理的结点后放一个空指针作为标记。如下

前序代码：

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> st;if(!root)return res;st.push(root);while(!st.empty()){TreeNode* cur = st.top();if(cur != nullptr){st.pop();if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left);st.push(cur);st.push(nullptr);}else{st.pop();TreeNode* node = st.top();st.pop();res.push_back(node->val);}}return res;}
};

中序代码：

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> st;if(!root)return res;st.push(root);while(!st.empty()){TreeNode* cur = st.top();if(cur != nullptr){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();TreeNode* node = st.top();st.pop();res.push_back(node->val);}}return res;}
};

后序代码：

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;stack<TreeNode*> st;if(root == nullptr)return res;st.push(root);while(!st.empty()){TreeNode* cur = st.top();if(cur!=nullptr){st.pop();st.push(cur); // 中st.push(nullptr);if(cur->right) st.push(cur->right);if(cur->left) st.push(cur->left);}else{st.pop();TreeNode* node = st.top();st.pop();res.push_back(node->val);}}return res;}
};