请写出二叉树前序遍历的实现，并说明其递归与迭代两种写法的时间与空间复杂度。

Question

Accepted Answer

考察点：考察二叉树遍历的基础实现与复杂度分析能力。回答思路：能写出正确的前序遍历代码，顺序为根左右 能说明递归实现的思路与时间复杂度O(n) 能说明迭代实现使用栈模拟，空间复杂度O(h) 能对比递归与迭代的空间开销差异

考察说明