/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ /*前序非递归de算法思想: 对于任意一个结点tmp: a.若栈不空,弹出栈顶结点,如果栈顶指针tmp的右孩子存在则 将右孩子入栈,如果左孩子存在则将左孩子入栈 b.直到栈空位置,遍历结束 */ class Solution { //private: // stack<TreeNode*> stk; public: vector<int> preorderTraversal(TreeNode* root) { stack <TreeNode*> stk; vector<int> out; if(!root) return out; TreeNode* tmp; stk.push(root); while(!stk.empty()) { tmp=stk.top(); out.push_back(tmp->val); stk.pop(); if(tmp->right){ stk.push(tmp->right); } if(tmp->left){ stk.push(tmp->left); } } return out; } };