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.
1import java.util.ArrayList;
2import java.util.List;
3
4class TreeNode {
5 int val;
6 TreeNode left;
7 TreeNode right;
8 TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public List<Integer> preorderTraversal(TreeNode root) {
13 List<Integer> res = new ArrayList<>();
14 preorder(root, res);
15 return res;
16 }
17
18 private void preorder(TreeNode node, List<Integer> res) {
19 if (node == null) return;
20 res.add(node.val);
21 preorder(node.left, res);
22 preorder(node.right, res);
23 }
24}The Java solution uses an ArrayList and a helper method to perform the preorder traversal. The helper method recursively visits nodes and adds their values to the list.
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;
using 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.