# LeetCode –Binary Tree Preorder Traversal

### 题目：

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input:

``` [1,null,2,3]
1
\
2
/
3

```

Output:

` [1,3,2]`

Follow up: 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) {

vector<int> res;
stack<TreeNode*> ss;
TreeNode *p = root;
while (!ss.empty()||p){
if (p!=NULL){
ss.push(p);
res.push_back(p->val);
p = p->left;
}
else{
p = ss.top();
ss.pop();
p=p->right;

}
}
return res;

}
};``````

### 实现：

• 递归实现
``````class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {

vector<int> res;
preorder(root, res);
return res;

}
void preorder(TreeNode *root, vector<int> &res){
if (!root) return;
res.push_back(root->val);
preorder(root->left, res);
preorder(root->right, res);
}
};``````

### 参考:

[LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历

Tree Preorder Traversal 3 different solutions