问题1：先序遍历（要求递归和迭代两种方式）

方法一：递归

树本身就有递归的特性，因此递归方法最简单，这里直接放上代码，需要说明的是，中序遍历，前序遍历和后序遍历可采用相同的代码模板完成实现。
时间复杂度：O(n)，n 为树的节点个数
空间复杂度：O(h)，h 为树的高度

文末免费送电子书：七月在线干货组最新 升级的《名企AI面试100题》免费送！

方法二：迭代

时间复杂度：O(n)，n 为树的节点个数

空间复杂度：O(h)，h 为树的高度

问题2：旋转数组寻找k

思路一：暴力解法

直接遍历整个数组，找到目标值target

代码如下：

时间复杂度：O(n)

空间复杂度：O(1)

思路二：二分查找

先要设置整个数组的左右两端端点：left = 0，right = len(nums) - 1

1、若 target == nums[mid]，直接返回

2、若 nums[left] <= nums[mid]，说明左侧区间 [left,mid]「连续递增」。此时：

若 nums[left] <= target <= nums[mid]，说明 target 位于左侧。令 right = mid-1，在左侧区间查找

否则，令 left = mid+1，在右侧区间查找

3、否则，说明右侧区间 [mid,right]「连续递增」。

此时：

若 nums[mid] <= target <= nums[right]，说明 target 位于右侧区间。令 left = mid+1，在右侧区间查找

否则，令 right = mid-1，在左侧区间查找

代码如下：

时间复杂度：O(logn)
空间复杂度：O(1)

帮助数千人成功上岸的《名企AI面试100题》书，电子版，限时免费送，评论区回复“100题”领取！

本书涵盖计算机语⾔基础、算法和⼤数据、机器学习、深度学习、应⽤⽅向 (CV、NLP、推荐 、⾦融风控)等五⼤章节，每⼀段代码、每⼀道题⽬的解析都经过了反复审查或review，但不排除可能仍有部分题⽬存在问题，如您发现，敬请通过官⽹/APP七月在线 - 国内领先的AI职业教育平台 (julyedu.com)对应的题⽬页⾯留⾔指出。

为了照顾⼤家去官⽹对应的题⽬页⾯参与讨论，故本⼿册各个章节的题⽬顺序和官⽹/APP题库内的题⽬展⽰顺序 保持⼀致。 只有100题，但实际笔试⾯试不⼀定局限于本100题，故更多烦请⼤家移步七⽉在线官⽹或 七⽉在线APP，上⾯还有近4000道名企AI笔试⾯试题等着⼤家，刷题愉快。