**一. 题目描述** 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 <iostream> #include <vector> 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<int> &k) { if (root != NULL) { k.push_back(root->val); preorder(root->left, k); preorder(root->right, k); } } vector<int> preorderTraversal(TreeNode *root) { vector<int> temp; preorder(root, temp); return temp; } }; ~~~ 非递归解法（stack实现）： ~~~ #include <iostream> #include <vector> #include <stack> using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL){} }; class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> temp; temp.clear(); stack<TreeNode *> 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; } }; ~~~