1.1 问题定义汉诺塔Tower of Hanoi是一个经典的递归问题起源于印度古老传说。问题描述如下有三根柱子A、B、CA柱上有n个大小不同的圆盘大盘在下小盘在上。要求将所有圆盘从A柱移动到C柱每次只能移动一个圆盘且在移动过程中任何时刻都不能出现大盘放在小盘上面的情况。1.2 递归解法思路汉诺塔问题的核心思想是分治法将复杂问题分解为规模更小的子问题将A柱上的n-1个圆盘借助C柱移动到B柱将A柱上剩下的最大圆盘直接移动到C柱将B柱上的n-1个圆盘借助A柱移动到C柱1.3 时间复杂度分析汉诺塔问题的递推关系式为T(n)2T(n−1)1,T(1)1T(n) 2T(n-1) 1, \quad T(1) 1T(n)2T(n−1)1,T(1)1求解过程展开递推式T(n)2T(n−1)12(2T(n−2)1)122T(n−2)2123T(n−3)2221…2n−1T(1)2n−2⋯212n−12n−2⋯212n−1 \begin{align*} T(n) 2T(n-1) 1 \\ 2(2T(n-2) 1) 1 2^2T(n-2) 2 1 \\ 2^3T(n-3) 2^2 2 1 \\ \dots \\ 2^{n-1}T(1) 2^{n-2} \dots 2 1 \\ 2^{n-1} 2^{n-2} \dots 2 1 \\ 2^n - 1 \end{align*}T(n)​2T(n−1)12(2T(n−2)1)122T(n−2)2123T(n−3)2221…2n−1T(1)2n−2⋯212n−12n−2⋯212n−1​因此汉诺塔问题的时间复杂度为O(2^n)属于指数级复杂度随着n的增长计算量会急剧增加。1.4 代码实现Pythondefhanoi(n,source,auxiliary,target):ifn1:print(f移动圆盘 1 从{source}到{target})return# 将n-1个圆盘从源柱移动到辅助柱hanoi(n-1,source,target,auxiliary)# 移动最大圆盘到目标柱print(f移动圆盘{n}从{source}到{target})# 将n-1个圆盘从辅助柱移动到目标柱hanoi(n-1,auxiliary,source,target)# 测试3个圆盘从A移动到Chanoi(3,A,B,C)1.5 空间复杂度分析递归实现的空间复杂度主要由递归栈的深度决定每次递归调用都会在栈中保存当前的状态。对于n个圆盘的汉诺塔问题递归深度为n因此空间复杂度为O(n)。二、二叉树遍历算法二叉树遍历是指按照某种顺序访问二叉树中的所有节点使得每个节点被访问且仅被访问一次。常见的遍历方式包括前序遍历、中序遍历和后序遍历每种遍历方式都有递归和非递归两种实现方法。2.1 二叉树节点定义首先定义二叉树的节点结构classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightright2.2 前序遍历Preorder Traversal遍历顺序根节点 → 左子树 → 右子树2.2.1 递归实现递归实现非常直观直接按照遍历顺序访问节点即可defpreorder_recursive(root):result[]defdfs(node):ifnotnode:returnresult.append(node.val)# 先访问根节点dfs(node.left)# 再遍历左子树dfs(node.right)# 最后遍历右子树dfs(root)returnresult2.2.2 非递归实现栈方法非递归实现需要借助栈来模拟递归过程defpreorder_iterative(root):ifnotroot:return[]result[]stack[root]whilestack:nodestack.pop()result.append(node.val)# 注意栈是后进先出所以先压入右子节点再压入左子节点ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult时间复杂度O(n)每个节点被访问一次。空间复杂度O(n)最坏情况下树退化为链表需要存储所有节点。2.3 中序遍历Inorder Traversal遍历顺序左子树 → 根节点 → 右子树对于二叉搜索树中序遍历可以得到有序序列。2.3.1 递归实现definorder_recursive(root):result[]defdfs(node):ifnotnode:returndfs(node.left)# 先遍历左子树result.append(node.val)# 再访问根节点dfs(node.right)# 最后遍历右子树dfs(root)returnresult2.3.2 非递归实现栈方法definorder_iterative(root):ifnotroot:return[]result[]stack[]currentrootwhilecurrentorstack:# 一直遍历到最左节点whilecurrent:stack.append(current)currentcurrent.left currentstack.pop()result.append(current.val)currentcurrent.rightreturnresult时间复杂度O(n)每个节点被访问一次。空间复杂度O(n)最坏情况下需要存储所有节点。2.4 后序遍历Postorder Traversal遍历顺序左子树 → 右子树 → 根节点2.4.1 递归实现defpostorder_recursive(root):result[]defdfs(node):ifnotnode:returndfs(node.left)# 先遍历左子树dfs(node.right)# 再遍历右子树result.append(node.val)# 最后访问根节点dfs(root)returnresult2.4.2 非递归实现双栈法后序遍历的非递归实现相对复杂常用双栈法defpostorder_iterative(root):ifnotroot:return[]stack1[root]stack2[]whilestack1:nodestack1.pop()stack2.append(node)ifnode.left:stack1.append(node.left)ifnode.right:stack1.append(node.right)# stack2中存储的是逆后序序列反转后得到后序遍历结果result[]whilestack2:result.append(stack2.pop().val)returnresult2.4.3 非递归实现单栈法也可以使用单个栈实现需要记录前一个访问的节点defpostorder_iterative_single_stack(root):ifnotroot:return[]result[]stack[]currentroot prevNonewhilecurrentorstack:whilecurrent:stack.append(current)currentcurrent.left currentstack[-1]# 如果右子节点为空或者已经被访问过则访问当前节点ifnotcurrent.rightorcurrent.rightprev:result.append(current.val)stack.pop()prevcurrent currentNoneelse:currentcurrent.rightreturnresult时间复杂度O(n)每个节点被访问一次。空间复杂度O(n)最坏情况下需要存储所有节点。2.5 三种遍历方式对比遍历方式顺序递归实现复杂度非递归实现复杂度典型应用场景前序遍历根 → 左 → 右简单中等复制二叉树、前缀表达式计算中序遍历左 → 根 → 右简单中等二叉搜索树的有序输出后序遍历左 → 右 → 根简单较复杂删除二叉树、后缀表达式计算2.6 递归与非递归实现对比实现方式优点缺点适用场景递归实现代码简洁、逻辑清晰可能出现栈溢出、性能稍低树深度较小、代码可读性优先非递归实现无栈溢出风险、性能更高代码相对复杂、逻辑较难理解树深度较大、性能要求较高三、总结汉诺塔问题是典型的递归分治问题时间复杂度为O(2^n)空间复杂度为O(n)展示了递归方法在解决复杂问题时的简洁性但也体现了指数级复杂度的局限性。二叉树遍历是树结构操作的基础前序、中序、后序三种遍历方式各有其应用场景。递归实现代码简洁直观而非递归实现虽然代码相对复杂但避免了递归栈溢出的风险在处理大规模二叉树时更加稳定。递归方法的核心是将问题分解为更小的子问题而非递归方法则通常需要借助栈等数据结构来模拟递归过程两种方法各有优劣需要根据具体场景选择合适的实现方式。