leetcode || 144、Binary Tree Preorder Traversal

problem：

Given a binary tree, return the preorder traversal 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?

Hide Tags   Tree Stack 題意：非遞歸前序周遊二叉樹

thinking：

（1）前序周遊的遞歸法很easy，本題要求非遞歸，借助stack實作

（2）思路是：不為空時，優先将節點的左孩子入棧，入棧時即通路節點值，如果左孩子為空，取棧頂節點，通路其右孩子，再重複上述步奏。

code：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
       vector<int> ret;
       stack<TreeNode *> _stack;
       TreeNode *node = root;
       while(node!=NULL ||!_stack.empty())
       {
           if(node!=NULL)
           {
               ret.push_back(node->val);
               _stack.push(node);
               node=node->left;
           }
           else
           {
               node=_stack.top();
               _stack.pop();
               node=node->right;
           }
           
       }
       return ret;
    }
};