Given a binary tree, return the preorder traversal of its nodes' values.
For example: Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
前序遍历，使用递归，就太简单了。
如何使用迭代的方式,其实就是使用栈模拟递归(注意递归(DFS)和栈的关系，队列和BFS的关系)
先访问节点，然后压入右孩子，压入左孩子.
vector<int> preorderTraversal(TreeNode *root) {
vector<int> result;
if (root == NULL)
return result;
stack<TreeNode *>s;
s.push(root);
while (!s.empty()) {
TreeNode *p = s.top();
s.pop();
result.push_back(p->val);
if (p->right)
s.push(p->right);
if (p->left)
s.push(p->left);
}
return result;
}