【Inorder Traversal】
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,3,2].
Note: Recursive solution is trivial, could you do it iteratively?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
思路：
preorder用栈两三下就写完了
vector<int> preorderTraversal(TreeNode *root) {
vector<int> nodes;
if(root == NULL) return nodes;
stack<TreeNode *> tStack;
tStack.push(root);
while(!tStack.empty()){
TreeNode *top = tStack.top();
nodes.push_back(top->val);
tStack.pop();
if(top->right != NULL)
tStack.push(top->right);
if(top->left != NULL)
tStack.push(top->left);
}
return nodes;
}
但是inorder不简单啊，模仿递归记录调用处然后处理完当前函数回来，下午困得不行闷头试了好几次各种bug超Memory，看了我是歌手回来发现脑子清醒了
vector<int> inorderTraversal(TreeNode *root) {
vector<int> nodes;
if(root == NULL) return nodes;
stack<TreeNode *> tStack;
TreeNode * cur = root;
while(!tStack.empty() || cur != NULL){//假如处理完根的左子树了，tStack也会为空
while(cur != NULL){
tStack.push(cur);//只要当前节点有左孩子，则必须先去访问左子树，而当前节点就得入栈；
cur = cur->left;
}
cur = tStack.top();//如果当前节点为空怎么办？当然就访问它的父节点了，也就是栈顶元素；
tStack.pop();
nodes.push_back(cur->val);//访问完栈顶元素之后就需要将当前节点置为栈顶元素的右孩子
cur = cur->right;
}
return nodes;
}
Postorder与Inorder很相似，但是比Inorder复杂的地方是如何判断该节点的左右子树都已经访问过了，按照Inorder的写法左子树还是先被访问，没有问题，但是访问完左子树后不能直接访问当前节点，要判断当前节点的右子树是否已经被访问，如果没有访问则应该继续去访问右子树，最后再访问当前节点
vector<int> postorderTraversal(TreeNode *root) {
vector<int> nodes;
if(root == NULL) return nodes;
stack<TreeNode *> tStack;
TreeNode *cur = root; //指向当前要检查的节点
TreeNode *previsited = NULL; //指向前一个被访问的节点
while (!tStack.empty() || cur != NULL) {
while (cur != NULL) { //只要cur有左孩子，则cur入栈，直到cur没有左孩子；
tStack.push(cur);
cur = cur->left;
}
cur = tStack.top();
if (cur->right == NULL || cur->right == previsited) {//当前节点的右孩子如果为空或者已经被访问，则访问当前节点
tStack.pop();//后序遍历访问序列中，当前节点的前驱必然是其右孩子（如果有的话））
nodes.push_back(cur->val);
previsited = cur;
cur = NULL;
}else { //否则访问右孩子，继续上述过程
cur = cur->right;
}
}
return nodes;
}