## Algorithm

Problem Name: 144. Binary Tree Preorder Traversal

Given the `root` of a binary tree, return the preorder traversal of its nodes' values.

Example 1:

```Input: root = [1,null,2,3]
Output: [1,2,3]
```

Example 2:

```Input: root = []
Output: []
```

Example 3:

```Input: root = [1]
Output: [1]
```

Constraints:

• The number of nodes in the tree is in the range `[0, 100]`.
• `-100 <= Node.val <= 100`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
struct TreeNode **stack, *node;
int ssz, sp;
int *p, psz, n;

if (!root) {
*returnSize = 0;
return NULL;
}

ssz = 100;
stack = malloc(ssz * sizeof(struct TreeNode *));
//assert(stack);
sp = 0;

psz = 100;
p = malloc(psz * sizeof(int));
//assert(p);
n = 0;

#define PUSH(N) do { \
if (ssz == sp) { \
ssz *= 2; \
stack = realloc(stack, ssz * sizeof(struct TreeNode *)); \
/* assert(stack); */ \
} \
stack[sp ++] = N; \
} while (0)

#define POP(N) do { N = stack[-- sp]; } while (0)

if (psz == n) { \
psz *= 2; \
p = realloc(p, psz * sizeof(int)); \
} \
p[n ++] = V; \
} while (0)

PUSH(root);
while (sp) {
POP(node);
if (node->right) PUSH(node->right);
if (node->left) PUSH(node->left);
}

*returnSize = n;

return p;
}
``````
Copy The Code &

Input

cmd
root = [1,null,2,3]

Output

cmd
[1,2,3]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector preorderTraversal(TreeNode* root) {
vectorres;
stacks;
auto p = root;
while(p || !s.empty()){
if(!p) p = s.top(), s.pop();
res.push_back(p->val);
if(p->right) s.push(p->right);
p = p->left;
}
return res;
}
};
``````
Copy The Code &

Input

cmd
root = [1,null,2,3]

Output

cmd
[1,2,3]

### #3 Code Example with C++ Another Programming

```Code - C++ Programming```

``````
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
vector preorderTraversal(TreeNode *root) {
vector ret;
if (!root) return ret;

stack s;
s.push(root);

while (!s.empty()) {
TreeNode *p = s.top();
s.pop();

if (p) {
ret.push_back(p->val);
s.push(p->right);
s.push(p->left);
}
}
return ret;
}
};
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const preorderTraversal = function(root) {
const res = [];
traversal(root, res);
return res;
};

function traversal(node, arr) {
if (node === null) return;
arr.push(node.val);
if (node.left) {
traversal(node.left, arr);
}
if (node.right) {
traversal(node.right, arr);
}
}
``````
Copy The Code &

Input

cmd
root = []

Output

cmd
[]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = [root]
q = [root]
while any(q):
tmp = []
for node in q:
if node.right:
res.insert(res.index(node) + 1, node.right)
tmp.append(node.right)
if node.left:
res.insert(res.index(node) + 1, node.left)
tmp.insert(-1, node.left)
q = tmp
return [j.val for j in res if j]
``````
Copy The Code &

Input

cmd
root = [1]

Output

cmd
[1]