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].
前序遍历二叉树，只不过题目的要求是尽量不要使用递归，当然我还是先用递归写了一个：
1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 vector<int> preorderTraversal(TreeNode* root) { 13 ret.clear(); 14 if(root != NULL) 15 preTrans(root); 16 return ret; 17 } 18 void preTrans(TreeNode * root){ 19 ret.push_back(root->val); 20 if(root->left != NULL) preTrans(root->left); 21 if(root->right != NULL) preTrans(root->right); 22 } 23 private: 24 vector<int> ret; 25 };
当然还有非递归的方法，递归那么当然要使用到stack，其实这种方法写起来有点像是java中的递归的迭代器：
1 class Solution { 2 public: 3 vector<int> preorderTraversal(TreeNode* root) { 4 vector<int> ret; 5 if(root == NULL) return ret; 6 stack<TreeNode*> treeStk; 7 treeStk.push(root); 8 TreeNode * tmpNode; 9 while(!treeStk.empty()){ 10 tmpNode = treeStk.top(); 11 treeStk.pop(); 12 ret.push_back(tmpNode->val); 13 if(tmpNode->left != NULL) treeStk.push(tmpNode->left); 14 if(tmpNode->right != NULL) treeStk.push(tmpNode->right); 15 } 16 return ret; 17 } 18 };
LeetCode OJ：Binary Tree Preorder Traversal（前序遍历二叉树）
原文：http://www.cnblogs.com/-wang-cheng/p/4898930.html