汉诺塔问题是经典递归问题，其递归关系推导如下

汉诺塔问题是经典递归问题其递归关系推导如下问题定义将n个圆盘从A柱移动到C柱借助B柱每次只能移动一个圆盘且大盘不能放在小盘上递推关系先将n-1个圆盘从A移到B需要T(n-1)步再将最大的圆盘从A移到C需要1步最后将n-1个圆盘从B移到C需要T(n-1)步因此得到递推式T(n) 2T(n-1) 1初始条件T(1)1求解递推式 展开可得T(n) 2^n - 1因此时间复杂度为O(2^n)空间复杂度为O(n)递归栈深度Python实现代码def hanoi(n, a‘A’, b‘B’, c‘C’):if n 1:print(f移动圆盘1从 {a} 到 {c}“)returnhanoi(n-1, a, c, b)print(f移动圆盘{n}从 {a} 到 {c}”)hanoi(n-1, b, a, c)测试3个圆盘的移动步骤hanoi(3)二、二叉树遍历实现首先定义二叉树节点结构class TreeNode:definit(self, val0, leftNone, rightNone):self.val valself.left leftself.right right1. 前序遍历根-左-右递归实现def preorder_recursive(root):res []def dfs(node):if not node:returnres.append(node.val)dfs(node.left)dfs(node.right)dfs(root)return res非递归实现栈def preorder_iterative(root):if not root:return []res, stack [], [root]while stack:node stack.pop()res.append(node.val)# 栈是后进先出先压右子节点再压左子节点if node.right:stack.append(node.right)if node.left:stack.append(node.left)return res2. 中序遍历左-根-右递归实现def inorder_recursive(root):res []def dfs(node):if not node:returndfs(node.left)res.append(node.val)dfs(node.right)dfs(root)return res非递归实现栈def inorder_iterative(root):res, stack [], []current rootwhile current or stack:# 一直走到最左子节点while current:stack.append(current)current current.leftcurrent stack.pop()res.append(current.val)current current.rightreturn res3. 后序遍历左-右-根递归实现def postorder_recursive(root):res []def dfs(node):if not node:returndfs(node.left)dfs(node.right)res.append(node.val)dfs(root)return res非递归实现双栈def postorder_iterative(root):if not root:return []stack1, stack2 [root], []while stack1:node stack1.pop()stack2.append(node)if node.left:stack1.append(node.left)if node.right:stack1.append(node.right)# stack2逆序即为后序遍历结果return [node.val for node in reversed(stack2)]复杂度说明三种遍历的时间复杂度均为O(n)每个节点访问一次空间复杂度递归实现最坏情况链状树为O(n)平均情况为O(log n)递归栈深度非递归实现最坏情况为