力扣144.二叉树的前序遍历145.二叉树的后序遍历94.二叉树的中序遍历（非递归版）

前序遍历

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; st.push(root); while(!st.empty()) { TreeNode* node = st.top(); st.pop(); if(node != nullptr) result.push_back(node->val); else continue; st.push(node->right); st.push(node->left); } return result; } };

后序遍历 这里的思路是交换了

st.push(node->right); st.push(node->left);

的顺序，从先序列遍历的根左右变成了根右左，接着通过reverse变成了左右根，即后序遍历。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; st.push(root); while(!st.empty()) { TreeNode* node = st.top(); st.pop(); if(node != nullptr) result.push_back(node->val); else continue; st.push(node->left); st.push(node->right); } reverse(result.begin(), result.end()); return result; } };

中序遍历 写法一：

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { if(cur != nullptr) { st.push(cur); cur = cur->left; } else { cur = st.top(); st.pop(); result.push_back(cur->val); cur = cur->right; } } return result; } };

写法二：

class Solution { public: vector<int> inorderTraversal(TreeNode* root) { vector<int> result; stack<TreeNode*> st; TreeNode* node = root; while (node || !st.empty()) { // 遍历整个树 while (node) { // 先遍历到最左 st.push(node); node = node->left; } node = st.top(); st.pop(); result.push_back(node->val); node = node->right; // 进入右子树 } return result; } };