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

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

问题定义：将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}“)
return
hanoi(n-1, a, c, b)
print(f"移动圆盘{n}从 {a} 到 {c}”)
hanoi(n-1, b, a, c)

测试：3个圆盘的移动步骤

hanoi(3)

二、二叉树遍历实现

首先定义二叉树节点结构：

class TreeNode:
definit(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

1. 前序遍历（根-左-右）

递归实现

def preorder_recursive(root):
res = []
def dfs(node):
if not node:
return
res.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 res

2. 中序遍历（左-根-右）

递归实现

def inorder_recursive(root):
res = []
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res

非递归实现（栈）

def inorder_iterative(root):
res, stack = [], []
current = root
while current or stack:
# 一直走到最左子节点
while current:
stack.append(current)
current = current.left
current = stack.pop()
res.append(current.val)
current = current.right
return res

3. 后序遍历（左-右-根）

递归实现

def postorder_recursive(root):
res = []
def dfs(node):
if not node:
return
dfs(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)（递归栈深度）

非递归实现：最坏情况为