Problem:
Given a binary tree, return the preorder traversal of its nodes‘ value.
For example:
Given binary tree {1, #, 2, 3},
return [1,2,3]
Note: Recursive solution is trivial, could you do it iteratively?
分析：
先序遍历的访问顺序是“中左右”，先遍历根节点，随后是左子树、右子树。每个节点第一次被访问时，直接加入遍历的序列中，此时左子树没有遍历，右子树也没有遍历，根据顺序需要先遍历左子树，左子树整个完成后遍历右子树，所以要将没有访问过右子树的根节点依次压入堆栈，在访问右子树分支的时候再弹出堆栈。
完整的逻辑是先从根节点开始走左子树，一直朝着左走到叶子节点，并将访问过的节点加入遍历过的序列中。而后，循环着查看堆栈顶部的元素，如果有右子树，则完整的遍历右子树，并在遍历前弹出栈顶元素；如果没有右子树，则直接弹出栈顶的元素。
1 class Solution { 2 public: 3 vector<int> preorderTraversal(TreeNode *root) { 4 vector<int> result; 5 stack<TreeNode *> stk; 6 TreeNode *p = root; 7 while(p != NULL) { 8 result.push_back(p->val); 9 stk.push(p); 10 p = p->left; 11 } 12 13 while(!stk.empty()) { 14 TreeNode *top = stk.top(); 15 if(top->right == NULL) { 16 stk.pop(); 17 } else { 18 TreeNode *p = top->right; 19 stk.pop(); 20 while(p != NULL) { 21 result.push_back(p->val); 22 stk.push(p); 23 p = p->left; 24 } 25 } 26 } 27 return result; 28 } 29 };
Binary Tree Preorder Traversal,布布扣,bubuko.com
Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/foreverinside/p/3697911.html