144. Binary Tree Preorder Traversal

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

For example:Given binary tree [1,null,2,3],

1 \ 2 / 3

return [1,2,3].

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

/** * Definition for a binary tree node. * 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) { if (root==NULL) { return vector<int>(); } vector<int> result; stack<TreeNode *> treeStack; treeStack.push(root); while (!treeStack.empty()) { TreeNode *temp = treeStack.top(); result.push_back(temp->val); treeStack.pop(); if (temp->right!=NULL) { //右节点存在则保存 treeStack.push(temp->right); } if (temp->left!=NULL) { //左节点存在则保存（后保存的先出栈） treeStack.push(temp->left); } } return result; } };