Leetcode#144 Binary Tree Preorder Traversal

原题地址

递归代码谁都会，当然是写非递归代码了。

最基本的写法是用一个特殊栈同时保存节点以及节点的左孩子、右孩子是否遍历过。这种思路比较简单，跟递归写法一样很好理解。前序、中序、后序的遍历写法类似。

还有一种更"屌"的写法，只需要使用普通栈即可，不需要保存左孩子、右孩子是否遍历过。基本思路是：

1. 只要当前节点还有左孩子，就一直压栈下去，直到没有左孩子了

2. 从栈顶依次弹栈，直到找到一个有右孩子的节点，返回1

对于前序和中序，无非是在1中访问节点的值，还是在2中访问节点的值罢了。

对于后序就没法这么做了，不过也有"屌"的写法，可以参考这篇文章。

代码：

 1 vector<int> preorderTraversal(TreeNode *root) {
 2         vector<int> res;
 3         stack<TreeNode *> st;
 4         TreeNode *node = NULL;
 5         
 6         node = root;
 7         while (node) {
 8             while (node) {
 9                 res.push_back(node->val);
10                 st.push(node);
11                 node = node->left;
12             }
13             node = NULL;
14             while (!st.empty() && !node) {
15                 node = st.top()->right;
16                 st.pop();
17             }
18         }
19         
20         return res;
21 }