[LeetCode] Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes’ values.

For example: Given binary tree {1,#,2,3},

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

递归实现代码/****************************************************************** @Author : 楚兴* @Date: 2015/2/23 18:27* @Status : Accepted* @Runtime : 4 ms******************************************************************/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> result;helper(root, result);return result;}void helper(TreeNode *root, vector<int>& num){if (root){num.push_back(root->val);helper(root->left, num);helper(root->right, num);}}};非递归实现代码1/****************************************************************** @Author : 楚兴* @Date: 2015/2/24 00:54* @Status : Accepted* @Runtime : 6 ms******************************************************************/class Solution {public:vector<int> preorderTraversal(TreeNode *root) {vector<int> result;stack<TreeNode*> nodes;TreeNode *p = root;if (p){nodes.push(p);while (!nodes.empty()){p = nodes.top();nodes.pop();result.push_back(p->val);if (p->right){nodes.push(p->right);}if (p->left){nodes.push(p->left);}}}return result;}};非递归实现代码2/****************************************************************** @Author : 楚兴* @Date: 2015/2/24 01:06* @Status : Accepted* @Runtime : 4 ms******************************************************************/class Solution {public:vector<int> preorderTraversal(TreeNode *root) {vector<int> result;stack<TreeNode*> nodes;TreeNode *p = root;while (p != NULL || !nodes.empty()){if (p != NULL){while(p != NULL){result.push_back(p->val);nodes.push(p);p = p->left;}}else{p = nodes.top()->right;nodes.pop();}}return result;}};

后序遍历的实现见博文Binary Tree Postorder Traversal

，筑起梦想的鸟巢，开始人生的长跑，领先每回的冲刺，