先是中序遍历
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> inorderTraversal(TreeNode *root) { vector<int>v; stack<TreeNode*>s; TreeNode* p = root; while(!s.empty() || p != NULL){ if(p != NULL){ s.push(p); p = p->left; }else { p = s.top(); s.pop(); v.push_back(p->val); p = p->right; } } return v; } };
然后是前序遍历
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int>v; if(root == NULL) return v; stack<TreeNode*>s; s.push(root); while(!s.empty()){ TreeNode *tmp = s.top(); s.pop(); v.push_back(tmp->val); if(tmp->right) s.push(tmp->right); if(tmp->left) s.push(tmp->left); } return v; } };
后序遍历
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<int> postorderTraversal(TreeNode *root) { stack<TreeNode*>s; vector<int>ans; if(root == NULL) return ans; TreeNode *p = root, *q; do{ while(p){ s.push(p); p = p->left; } q = NULL; while(!s.empty()){ p = s.top(); s.pop(); if(p->right == q){ ans.push_back(p->val); q = p; }else { s.push(p); p = p->right; break; } } }while(!s.empty()); return ans; } };
or
vector<int> postorderTraversal(TreeNode *root) { vector<int> v; if (!root) return v; stack<TreeNode *> s; s.push(root); TreeNode *p = NULL; while(!s.empty()) { p = s.top(); s.pop(); v.insert(v.begin(), p->val); if (p->left) s.push(p->left); if (p->right) s.push(p->right); } return v; }