一. 题目描述

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

二. 题目分析

可使用递归解法，而只要是能用递归，也就是说能用栈来还原递归过程，因此方法不止一种。

使用栈来实现二叉树的遍历：首先在stack中压入当前的root，由于是前序遍历，故树是按照先根，然后左子树和后右子树进行访问，故pop取出一个结点，将它的value加入访问序列。之后压入它的右子树和左子树。直到stack为空。

三. 示例代码

递归解法：

#include 
   
     #include 
    
      using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL){} }; class Solution { public: void preorder(TreeNode *root, vector
     
       &k) { if (root != NULL) { k.push_back(root->val); preorder(root->left, k); preorder(root->right, k); } } vector
      
        preorderTraversal(TreeNode *root) { vector
       
         temp; preorder(root, temp); return temp; } }; 
       
      
     
    
   

非递归解法（stack实现）：

#include 
   
     #include 
    
      #include 
     
       using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL){} }; class Solution { public: vector
      
        preorderTraversal(TreeNode *root) { vector
       
         temp; temp.clear(); stack
        
          k; if (root == NULL) return temp; k.push(root); while (!k.empty()) { TreeNode *node = k.top(); k.pop(); temp.push_back(node->val); if (node->right != NULL) k.push(node->right); if (node->left != NULL) k.push(node->left); } return temp; } };