# Binary Tree Depth Order Traversal

# Binary Tree Preorder Traversal

> 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?

```c++
class Solution {
public:
vector preorderTraversal(TreeNode *root) {
vector vals;
if(root == NULL) {
return vals;
}

vector nodes;

//首先将root压栈
nodes.push_back(root);

while(!nodes.empty()) {
TreeNode* n = nodes.back();
vals.push_back(n->val);

//访问了该节点，出栈
nodes.pop_back();

//如果有右子树，压栈保存
if(n->right) {
nodes.push_back(n->right);
}

//如果有左子树，压栈保存
if(n->left) {
nodes.push_back(n->left);
}
}

return vals;
}
};
```

# Binary Tree Inorder Traversal

```c++
class Solution {
public:
vector inorderTraversal(TreeNode *root) {
vector vals;
if(root == NULL) {
return vals;
}

vector nodes;
TreeNode* p = root;
while(p || !nodes.empty()) {
//这里一直遍历左子树，将根节点压栈
while(p) {
nodes.push_back(p);
p = p->left;
}

if(!nodes.empty()) {
p = nodes.back();
vals.push_back(p->val);

//将根节点弹出，获取右子树
nodes.pop_back();
p = p->right;
}
}

return vals;
}
};
```

# Binary Tree Postorder Traversal

```c++
class Solution {
public:
vector postorderTraversal(TreeNode *root) {
vector vals;
if(root == NULL) {
return vals;
}

vector nodes;
TreeNode* pre = NULL;

nodes.push_back(root);

while(!nodes.empty()) {
TreeNode* p = nodes.back();
//如果不判断pre，我们就没法正确地出栈了
if((p->left == NULL && p->right == NULL) ||
(pre != NULL && (pre == p->left || pre == p->right))) {
vals.push_back(p->val);
nodes.pop_back();
pre = p;
} else {
//右子树压栈
if(p->right != NULL) {
nodes.push_back(p->right);
}

//左子树压栈
if(p->left != NULL) {
nodes.push_back(p->left);
}
}
}

return vals;
}
};
```

## 总结