144. Binary Tree Preorder Traversal
前序的非递归遍历：用堆来实现
如果把这个代码改成先向堆存储左节点再存储右节点，就变成了每一行从右向左打印
如果用队列替代堆，并且先存储左节点，再存储右节点，就变成了逐行打印
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if(root == NULL)
return result;
stack<TreeNode*> sta;
sta.push(root);
while(!sta.empty()){
TreeNode* node = sta.top();
sta.pop();
result.push_back(node->val);
if(node->right)
sta.push(node->right);
if(node->left)
sta.push(node->left);
}
return result;
}
};
94. Binary Tree Inorder Traversal
思路：用一个变量node记录当前节点，每次先遍历并存储所有的左节点直到为空，然后栈里顶部存储的那个节点就是最近父节点，然后再去遍历一个右节点，在右节点中继续寻找左节点
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> container;
TreeNode* cur = root;
while(cur || !container.empty()){
while(cur){
container.push(cur);
cur = cur->left;
}
cur = container.top();
container.pop();
result.push_back(cur->val);
cur = cur->right;
}
return result;
}
};
145. Binary Tree Postorder Traversal
http://www.cnblogs.com/grandyang/p/4251757.html的第二种方法
思路：前序遍历是中->左->右，后序遍历是左->右->中。在前序遍历的基础上，insert到begin的方式相当于把顺序全调换了，即变成了右->左->中，这个时候只需要再调换依稀右和左就能变成后序遍历的顺序。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
if(root == NULL)
return result;
stack<TreeNode*> sta;
sta.push(root);
while(!sta.empty()){
TreeNode* node = sta.top();
sta.pop();
result.insert(result.begin(),node->val);
if(node->left)
sta.push(node->left);
if(node->right)
sta.push(node->right);
}
return result;
}
};
173. Binary Search Tree Iterator
这个题其实就是中序非递归遍历，并且就是另一种写法的实现，也就是先在循环外将左节点全部装入stack
注意：初始化只是将第一次所有的左节点装入stack，next是一次一次的递归
class BSTIterator {
public:
BSTIterator(TreeNode* root) {
while(root){
sta.push(root);
root = root->left;
}
}
/** @return the next smallest number */
int next() {
TreeNode* node = sta.top();
sta.pop();
TreeNode* root = node->right;
while(root){
sta.push(root);
root = root->left;
}
return node->val;
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !sta.empty();
}
stack<TreeNode*> sta;
};