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)
#define add2p(V) do { \
if (psz == n) { \
psz *= 2; \
p = realloc(p, psz * sizeof(int)); \
} \
p[n ++] = V; \
} while (0)
PUSH(root);
while (sp) {
POP(node);
add2p(node->val);
if (node->right) PUSH(node->right);
if (node->left) PUSH(node->left);
}
*returnSize = n;
return p;
}
Input
root = [1,null,2,3]
Output
[1,2,3]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int>res;
stack < TreeNode*>s;
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;
}
};
Input
root = [1,null,2,3]
Output
[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<int> preorderTraversal(TreeNode *root) {
vector<int> ret;
if (!root) return ret;
stack < TreeNode *> 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;
}
};
Input
root = []
Output
[]
#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);
}
}
Input
root = []
Output
[]
#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]
Input
root = [1]
Output
[1]