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.
1using System;
2using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<int> PreorderTraversal(TreeNode root) {
List<int> res = new List<int>();
if (root == null) return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.Count > 0) {
TreeNode node = stack.Pop();
res.Add(node.val);
if (node.right != null) stack.Push(node.right);
if (node.left != null) stack.Push(node.left);
}
return res;
}
}C# implementation employs a Stack class to systematically handle traversal. This iteration strategy effectively manages binary trees of all sizes, bypassing recursion limits.