二叉樹 遍歷迭代法

Leetcode 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> inorderTraversal(TreeNode* root) {
//         stack<TreeNode*> st;
//         vector<int> path;
//         if(root == nullptr) return path;
//         st.push(root);//         while(!st.empty()){
//             TreeNode* cur = st.top();
//             st.pop();
//             path.push_back(cur->val);  // 中
//             if(cur->right != nullptr) st.push(cur->right);  // 右
//             if(cur->left != nullptr) st.push(cur->left);  // 左
//         }
//         return path;
//     }
// };// 中序迭代
class Solution{
public:vector<int> inorderTraversal(TreeNode* root){stack<TreeNode*> st;vector<int> path;TreeNode* cur = root;while(cur != nullptr || !st.empty()){if(cur != nullptr){st.push(cur);cur = cur->left;  // 左}else{cur = st.top();st.pop();path.push_back(cur->val);  // 中cur = cur->right;  // 右}}return path;}
};// 后序迭代  左右中，將之前前序中左右->中右左->（反轉）左右中
// class Solution {
// public:
//     vector<int> inorderTraversal(TreeNode* root) {
//         stack<TreeNode*> st;
//         vector<int> path;
//         if(root == nullptr) return path;
//         st.push(root);//         while(!st.empty()){
//             TreeNode* cur = st.top();
//             st.pop();
//             path.push_back(cur->val);  // 中
//             if(cur->left != nullptr) st.push(cur->left);  // 左
//             if(cur->right != nullptr) st.push(cur->right);  // 右
//         }
//         reverse(path.begin(), path.end());
//         return path;
//     }
// };