**一. 題目描述** 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; } }; ~~~