Given a binary tree, return the preorder traversal of its nodes' values.
Given a binary tree, return the postorder traversal of its nodes' values.
问题描述：给定一个二叉树，返回它的先序和后序遍历序列。
这里给的是先序和后序，中序遍历可以参考Binary Tree Inorder Traversal。
先来看先序，先序和中序类似，只是访问的顺序不太一样。
class Solution {
public:
vector
preorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
stack
sta; TreeNode *pnode = root; vector
vec; while(pnode || !sta.empty()) { while(pnode) { vec.push_back(pnode->val); sta.push(pnode); pnode = pnode->left; } if(!sta.empty()) { pnode = sta.top(); sta.pop(); pnode = pnode->right; } } return vec; } };
上面就是先序遍历的代码，当pnode不空或者栈不空时则循环，然后在循环中访问当前节点，然后将当前节点压入栈中，接着当前节点设置为左孩子，执行同样的操作，直到当前节点为空。然后查看栈，如果栈不空，就获取栈顶元素并弹出栈顶元素，然后将当前节点设为右孩子。重复上面的操作，代码和中序基本类似，处理vec.push_back()操作放的地方不一样。
再来看看后序，后序相对复杂，主要复杂的地方在于，当获取栈顶节点的时候是否该访问它呢？也就是说，它的右孩子是否已经访问了呢？
因此，在后序遍历时，栈中的元素除了包含节点指针外，还包含一个标志节点是否访问的变量。下面的代码主要是参考二叉树的非递归后序遍历算法。
class Solution {
public:
vector
postorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
stack
> sta; TreeNode *pnode = root; vector
vec; pair
ptnode; //从根节点开始，往左下方走，一直走到头，将路径上的每个节点入栈 while(pnode) { sta.push(make_pair(pnode, 0)); //压入栈的有两个信息，一是节点指针，二是其右节点是否被访问过 pnode = pnode->left; } while(!sta.empty()) { //当栈非空时 ptnode = sta.top(); //获取栈顶元素 //若其右孩子已经被访问过，或是该元素没有右孩子，则由后序遍历的定义，此时就可以访问这个节点了 if(!ptnode.first->right || ptnode.second) { ptnode = sta.top(); sta.pop(); vec.push_back(ptnode.first->val); } else { //若其右孩子存在且它的右孩子没有被访问过，就去处理其右孩子 ptnode.second = 1; sta.pop(); sta.push(ptnode); pnode = ptnode.first->right; while(pnode) { sta.push(make_pair(pnode, 0)); pnode = pnode->left; } } } return vec; } };
小结：
先序：在先序遍历的非递归遍历中，是先沿着左孩子一直遍历，边遍历边访问，然后压入栈中，直到节点为空，然后取栈顶元素，此时，由于它的左孩子在它之后入栈，可以断定，它本身和它的左孩子一定已经被访问过了，按照先序遍历的规则，于是将节点设置为右孩子，然后开始下一轮遍历，也就是说，现在可以访问右子树了。
中序：在中序遍历的非递归遍历中，也是先沿着左孩子一直遍历，但是此时并不访问，只是沿着左孩子将节点都压入栈中，直到当前节点为空，然后取栈顶元素，由于它的左孩子在它之后入栈，因此，当前栈顶节点的左孩子必定已经被访问过了，于是访问当前节点，然后将节点设置为右孩子，开始下一轮遍历。
后序：在后序遍历的非递归遍历中，也是先沿着左孩子，一直遍历，但是此时并不访问，而且在向栈中压入节点时，同时还要保存一个标志信息（标志该节点的右孩子是否被访问过）。然后取栈顶节点，因为栈顶节点的左孩子是在它之后入栈的，因此，它的左孩子一定已经被访问过了，根据后序遍历规则，此时，如果右孩子被访问了，则访问栈顶节点，那么，如何知道右孩子是否被访问了呢？就是之前保存在栈中的标志信息的作用了。如果栈顶节点没有右孩子或者它的右孩子已经被访问过了，此时，就应该访问栈顶节点，并将栈顶节点弹出；否则，就应该访问右子树，但是，在访问右子树之前，应该将当前栈顶节点的标志信息设为1（表示它的右子树已经访问了），然后访问右子树。于是，后序的非递归遍历也可以这样：
class Solution {
public:
vector
postorderTraversal(TreeNode *root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
stack
> sta; TreeNode *pnode = root; vector
vec; pair
ptnode; while(pnode || !sta.empty()) { while(pnode) { sta.push(make_pair(pnode, 0)); pnode = pnode->left; } if(!sta.empty()) { ptnode = sta.top(); if(!ptnode.first->right || ptnode.second) { sta.pop(); vec.push_back(ptnode.first->val); } else { ptnode.second = 1; sta.pop(); sta.push(ptnode); pnode = ptnode.first->right; } } } return vec; } };