LeetCode 144：Binary Tree Preorder Traversal（前序遍历）
Given a binary tree, return thepreordertraversal of its nodes’ values.
For example:Given binary tree{1,#,2,3},
1\2/ 3
return[1,2,3].
Note:Recursive solution is trivial, could you do it iteratively?
题目要求对二叉树进行非递归的前序遍历，所谓前序遍历即，先访问根节点、再访问左子树、然后是右子树。通常采用递归的方法，题目要求采用非递归的方法实现。算法如下：
1）如果根节点非空，将根节点加入到栈中。
2）如果栈不空，弹出出栈顶节点，将其值加加入到数组中。
如果该节点的右子树不为空，将右子节点加入栈中。
如果左子节点不为空，将左子节点加入栈中。
3）重复第二步，直到栈空。
class Solution {public:vector<int> preorderTraversal(TreeNode* root) {vector<int> result;stack< TreeNode *> node_stack;if (root != NULL) {node_stack.push(root);}while (!node_stack.empty()) {TreeNode * tmpNode = node_stack.top();node_stack.pop();result.push_back(tmpNode->val);if (tmpNode->right) {node_stack.push(tmpNode->right);}if (tmpNode->left) {node_stack.push(tmpNode->left);}}return result;}};LeetCode 94：Binary Tree Inorder Traversal（中序遍历）
Given a binary tree, return theinordertraversal of its nodes’ values.
For example:Given binary tree{1,#,2,3},
1\2/ 3
return[1,3,2].
题目要求对二叉树进行非递归的中序遍历，所谓前序遍历即，先访问左子树、再访问根节点、然后是右子树。通常采用递归的方法，题目要求采用非递归的方法实现。算法如下：
1）如果根节点非空，将根节点加入到栈中。
2）如果栈不空，取栈顶元素（暂时不弹出），
如果左子树已访问过，或者左子树为空，则弹出栈顶节点，将其值加入数组，如有右子树，将右子节点加入栈中。
如果左子树不为空，切未访问过，则将左子节点加入栈中，并标左子树已访问过。
3）重复第二步，直到栈空。
//包裹结构体，标明左子树是否已经访问过 struct TreeNodeWrapper{struct TreeNode *pNode;bool lVisited; //左子树已访问过bool rVisited; //右子树已访问过TreeNodeWrapper(TreeNode * p){pNode = p; lVisited= false; rVisited= false;}};class Solution {public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNodeWrapper*> node_stack;if (root == NULL)return result;node_stack.push(new TreeNodeWrapper(root));while(!node_stack.empty()){TreeNodeWrapper* pNode = node_stack.top();if (pNode->lVisited || pNode->pNode->left==NULL) //左子树已访问过，或者为空{node_stack.pop();result.push_back(pNode->pNode->val); //访问节点，访问右子树if (pNode->pNode->right){node_stack.push(new TreeNodeWrapper(pNode->pNode->right));}delete pNode;}else{//访问左子树，并标记node_stack.push(new TreeNodeWrapper(pNode->pNode->left));pNode->lVisited = true;}}return result;}};
方法二，不使用包裹结构体。上面的解法虽然原理上比较简单，当使用了一个包裹结构体，和大量的New/delete操作，显得比较复杂。不如下面这种算法比较简洁。
class Solution {public:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack< TreeNode *> node_stack;TreeNode * pNode = root;while (pNode || !node_stack.empty()) {//节点不为空，加入栈中，并访问节点左子树if (pNode != NULL) {node_stack.push(pNode);pNode = pNode->left;}else{//节点为空，从栈中弹出一个节点，访问这个节点， pNode = node_stack.top();node_stack.pop();//访问节点右子树 result.push_back(pNode->val);pNode = pNode->right;}}return result;}};
LeetCode 145：Binary Tree Postorder Traversal（后序遍历）
Given a binary tree, return thepostordertraversal of its nodes’ values.
For example:Given binary tree{1,#,2,3},
1\2/ 3
return[3,2,1].
题目要求对二叉树进行非递归的后序遍历，所谓后序遍历即，先访问左子树、然后是右子树，最后访问根节点。通常采用递归的方法，题目要求采用非递归的方法实现。算法如下：
1）如果根节点非空，将根节点加入到栈中。
2）如果栈不空，取栈顶元素（暂时不弹出），
希望你灰暗的心情在此刻明亮起来，去迎接美好的明天!
