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?

递归方式很简单：

1 vector
     
       preorderTraversal(TreeNode *root)  2     { 3         vector
      
        vtree; 4         preorder(vtree, root); 5         return vtree; 6     } 7      8     void preorder(vector
       
         &vtree, TreeNode *root) 9     {10         if (root == NULL)11             return;12         vtree.push_back(root->val);13         preorder(vtree, root->left);14         preorder(vtree, root->right);15     }
       
      
     

对于非递归方式，需要借助堆栈来临时存储tree node

1) if current node P is not empty, visit it and put P->right in stack, then P = P->left

2) else, get the top node in stack

1 vector
     
       preorderTraversal(TreeNode *root)  2     { 3         vector
      
        vtree; 4         stack
       
         stree; 5         TreeNode *visit = root; 6          7         while (!stree.empty() || (visit != NULL)) 8         { 9             if (visit != NULL)  10             {  11                 vtree.push_back(visit->val); // if visit is not empty, visit it12                 if (visit->right != NULL)   // if visit->right exit, push it in stack13                     stree.push(visit->right);14                 visit = visit->left;15             }16             else    // visit is null17             {18                 visit = stree.top();19                 stree.pop();20             }21         }22         23         return vtree;24     }