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?
首先需要明确前序遍历的顺序，即：节点 -> 左孩子 -> 右孩子，这一顺序进行遍历。
此题有一个比较讨巧的办法，就是在Solution类中声明一个vector成员变量，这样就能通过递归的方法往vector里push元素了。但是如果要求必须只通过给出的函数来解决这个问题的话，那么就需要使用“栈”这一数据结构来模拟函数的递归调用，具体方法可参考实现的代码。
/** * 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) { vector<int> result; stack<TreeNode*> node_stack; node_stack.push(root); while(!node_stack.empty()) { TreeNode *node = node_stack.top(); node_stack.pop(); if (node == NULL) { continue; } result.push_back(node->val); node_stack.push(node->right); node_stack.push(node->left); } return result; } };
【LeetCode】144. Binary Tree Preorder Traversal
原文：http://www.cnblogs.com/jdneo/p/4742582.html