//前序遍历
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
        stack<TreeNode*>stack;
        TreeNode *p = root;
        vector<int>array;
        while(!stack.empty() || p) {
            while (p) {
                array.push_back(p->val);
                stack.push(p);
                p = p->left;
            }
            
            if (!stack.empty()) {
                p = stack.top();
                stack.pop();
                p = p->right;
            }
        }
        return array;
    }
};