前序遍歷：根左右
//用棧來實現非遞歸解法
/*** Definition for a binary tree node.* 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> res;if(root == NULL)return res;stack<TreeNode*> stack;stack.push(root);while(!stack.empty()){TreeNode* c = stack.top();stack.pop();res.push_back(c->val);if(c->right)stack.push(c->right);if(c->left)stack.push(c->left);}return res;} };
//遞歸解法，注意res是全局的，要放在遍歷函數外面
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/ class Solution { public:vector<int> res;vector<int> preorderTraversal(TreeNode* root) {if(root){res.push_back(root->val);preorderTraversal(root->left);preorderTraversal(root->right);}return res;} };
中序遍歷：左根右
/*** Definition for a binary tree node.* 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) {stack<TreeNode*> st;vector<int> res;if(root == NULL) return res; //若根節點為空則返回空TreeNode* p = root;while(p || !st.empty()){while(p){//先將根節點入棧，再將它所有的左節點入棧 st.push(p);p = p->left; }p = st.top();st.pop();res.push_back(p->val);p = p->right;}return res;} };
?后序遍歷：左右根
可以使其遍歷順序為根左右，然后逆序插入vector中，即每次在vector的頭部插入結點值。在壓入棧時先壓入右結點再壓入左結點則在出棧時就是先左后右了。
//解法一
/*** Definition for a binary tree node.* 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) {if(!root) return {};vector<int> res;stack<TreeNode*> s{{root}};while(!s.empty()){TreeNode* t = s.top();s.pop();res.insert(res.begin(), t->val);if(t->left) s.push(t->left);if(t->right) s.push(t->right);}return res;} };
解法二：關鍵是判斷當前這個結點：
1）它如果有左右結點是否已經入棧，若沒有入棧則先將它的右結點入棧，再左結點入棧；如果它的左右結點已經入棧，則這個結點就可以直接加入容器vector里了。
2）如果它是葉子結點（沒有左右結點），則直接加入vector中。
/*** Definition for a binary tree node.* 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) {if(!root) return {};vector<int> res;stack<TreeNode*> s{{root}};TreeNode* head = root; //head初始化while(!s.empty()){TreeNode* t = s.top();if((!t->left && !t->right) || t->left==head || t->right==head){//當t為葉子結點 或t的左結點或右結點為head，即已經入棧了res.push_back(t->val);s.pop();head = t;}else{if(t->right) s.push(t->right);if(t->left) s.push(t->left);}}return res;} };
?
leetcode已經分別定義了類NestedInteger中的三個函數：
1）isInteger()：若當前這個NestedInteger是單個整數返回true；
2）getInteger()：返回當前這個單個的整數；
3）getList()：返回當前這個列表。
/*** // This is the interface that allows for creating nested lists.* // You should not implement it, or speculate about its implementation* class NestedInteger {* public:* // Return true if this NestedInteger holds a single integer, rather than a nested list.* bool isInteger() const;** // Return the single integer that this NestedInteger holds, if it holds a single integer* // The result is undefined if this NestedInteger holds a nested list* int getInteger() const;** // Return the nested list that this NestedInteger holds, if it holds a nested list* // The result is undefined if this NestedInteger holds a single integer* const vector<NestedInteger> &getList() const;* };*/ class NestedIterator { public:stack<NestedInteger> s;NestedIterator(vector<NestedInteger> &nestedList) {for(int i=nestedList.size()-1; i>=0; i--)//倒序插入 是為了彈出時是正序的 s.push(nestedList[i]);}int next() {//返回下一項的值NestedInteger t = s.top();s.pop();return t.getInteger(); //獲取對應整數 }bool hasNext() {//若下一項有值，返回truewhile(!s.empty()){NestedInteger t = s.top();if(t.isInteger())return true; //若下一個數是單個整數，返回true s.pop();//若下一個數是一個列表,使用getList()得到列表的每個整數倒序插入到棧中for(int i=t.getList().size()-1; i>=0; i--)s.push(t.getList()[i]);}return false;} };/*** Your NestedIterator object will be instantiated and called as such:* NestedIterator i(nestedList);* while (i.hasNext()) cout << i.next();*/
?
)
