前序遍历的递归写法是显然的，这里只给出非递归的解法（用栈实现）。 时间复杂度:O(N) C++代码：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if (root == nullptr)
return {};
vector<int> result;
stack<TreeNode*> record;
TreeNode* temp = root;
while (temp != nullptr || !record.empty())
{
while (temp != nullptr)
{
result.push_back(temp->val);
record.push(temp);
temp = temp->left;
}
if (!record.empty())
{
temp = record.top();
record.pop();
temp = temp->right;
}
}
return result;
}
};
