Sponsored
Sponsored
The recursive approach naturally aligns with the definition of preorder traversal: visit the root first, then recursively traverse the left subtree, followed by the right subtree.
Time Complexity: O(N) where N is the number of nodes, as each node is visited once. Space Complexity: O(N) in the worst case due to recursion stack space.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10void preorder(struct TreeNode* root, int* result, int* count) {
11 if (root == NULL) return;
12 result[(*count)++] = root->val;
13 preorder(root->left, result, count);
14 preorder(root->right, result, count);
15}
16
17int* preorderTraversal(struct TreeNode* root, int* returnSize) {
18 int* result = (int*)malloc(100 * sizeof(int));
19 *returnSize = 0;
20 preorder(root, result, returnSize);
21 return result;
22}This C code defines a recursive function for the preorder traversal. It allocates space for the result and uses a helper function to populate the preorder values by traversing each node recursively.
The iterative approach replaces the recursive call stack with an explicit stack. Nodes are processed in preorder, using a stack to maintain traversal state.
Time Complexity: O(N), since each node is visited once. Space Complexity: O(N), for the stack used to store nodes.
1#include <iostream>
2#include <vector>
#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector<int> preorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
stack<TreeNode*> stk;
stk.push(root);
while (!stk.empty()) {
TreeNode* node = stk.top();
stk.pop();
res.push_back(node->val);
if (node->right) stk.push(node->right);
if (node->left) stk.push(node->left);
}
return res;
}The C++ solution utilizes the STL stack to maintain a record of nodes yet to be explored. The iterative structure eliminates recursion, improving stack safety.