非递归用栈实现先序遍历
#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) {} }; stack<TreeNode*> st; class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> v; TreeNode *p; while(root || !st.empty()) { while(root) { v.push_back(root->val); st.push(root); root = root->left; } if(!st.empty()) { root = st.top();st.pop(); } root = root->right; } return v; } }; int main(void) { Solution s; /* TreeNode *root = new TreeNode(1); TreeNode *node1 = new TreeNode(2); root->right = node1; TreeNode *node2 = new TreeNode(3); node1->left = node2;*/ /* TreeNode *root = new TreeNode(1); TreeNode *node1 = new TreeNode(4); root->left = node1; TreeNode *node2 = new TreeNode(3); root->right = node2; TreeNode *node3 = new TreeNode(2); node1->left = node3;*/ /* TreeNode *root = new TreeNode(3); TreeNode *node2 = new TreeNode(1); root->right = node2; TreeNode *node3 = new TreeNode(2); node2->left = node3;*/ TreeNode *root = new TreeNode(2); TreeNode *node1 = new TreeNode(1); root->left = node1; TreeNode *node2 = new TreeNode(3); root->right = node2; TreeNode *node3 = new TreeNode(4); node1->right = node3; vector<int> re = s.preorderTraversal(root); vector<int>::iterator iter; for(iter = re.begin(); iter != re.end(); ++iter) { cout << *iter << endl; } return 0; }