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.
1class TreeNode:
2 def __init__(self, x):
3 self.val = x
4 self.left = None
5 self.right = None
6
7def preorderTraversal(root):
8 result = []
9 def preorder(node):
10 if not node:
11 return
12 result.append(node.val)
13 preorder(node.left)
14 preorder(node.right)
15 preorder(root)
16 return resultPython makes use of a nested helper function for the recursive traversal, adding node values directly to a list. The solution is concise and functional.
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.