LintCode (66) Binary Tree Preorder

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

Have you met this question in a real interview? 

Yes

Example

Given binary tree {1,#,2,3}:

1
 \
  2
 /
3

return [1,2,3].

Challenge

Can you do it without recursion?

因为不让用递归，那就虚拟一个stack好了， 因为preorder 是先current, 然后preorder(left), preorder(right), 在系统上其实是right先入，left后入。 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

/** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: Preorder in vector which contains node values. */ vector<int> preorderTraversal(TreeNode *root) { // write your code here vector<int> result; if (!root) return result; stack<TreeNode*> stk; stk.push(root); while(!stk.empty()){ TreeNode* cur= stk.top(); result.push_back(cur->val); stk.pop(); if (cur->right) stk.push(cur->right); if (cur->left) stk.push(cur->left); } return result; } };