常见递归模式

 

---

递归模式

常见递归模式

• 遍历二叉树模式
• 回溯模式
• 子问题分解模式
   

---

遍历二叉树模式

只要涉及递归的问题都是树的问题或者说树的遍历。

void traverse(TreeNode root) { // 遍历二叉树
    if (root == null) return;  // 递归结束条件
    print(root.val)            // 前序位置在进入左节点前输出当前节点
    traverse(root.left);       // 进入左子树
    print(root.val)            // 在中序位置在进入右节点前输出当前节点
    traverse(root.right);      // 进入右子树
    print(root.val)            // 在后序位置离开后节点后输出当前节点
}

这个代码的关键在于时机。下图是可视化过程

这里主要强调前序、后序的区别。

• 前序能解决的问题遍历二叉树直接计算出来
• 后序能解决的问题遍历二叉树直接计算出来及遍历完子树之后才能计算出来。

递归函数二叉树的每一个节点需要做什么回溯模式、分解子问题模式需要在什么时候前\中\后序做。
 

---

回溯模式

使用场景问题可通过遍历一棵二叉树得到答案。

ans = []
void recall( 路径[选择列表] )
	if 满足结束条件
		ans.add( 路径 )
		return
		
	for 选择 in [选择列表]
		做选择
		recall( 路径[选择列表] )
		撤销选择

回溯框架本质是遍历一颗决策树。

• 路径已经做出的选择
• 选择列表当前可以做的选择
• 结束条件到了决策树底层无法再做选择

核心在于 for 循环里面的递归在递归之前做选择在递归之后撤销选择。

• for 循环如果可视化就是在遍历一颗 N 叉树

问题是选择和撤销选择是在这颗树上做什么呢

• 选择是在这棵树上做前序遍历
• 撤销选择是在这颗树上做后序遍历

选择是在进入树的某一节点前执行。

撤销选择是在离开树的某一节点后执行。

做选择在进入节点前从选择列表拿出一个选择将它放入路径。

撤销选择在离开节点后从路径中拿出一个选择将它恢复到选择列表中。
 

---

子问题分解模式

使用场景可通过子问题/子树的答案推导出原问题的答案。

原问题分解成当前节点 + 左右子树的子问题。

int dp(TreeNode root) {        // 版本一
    if (root == null) 
		return 0;
		
    // 分解子问题的规模为n/2求出前半部分的最值和后半部分的最值
    int left = dp(root.left);
	int right = dp(root.right);
 
    // 合并在把前半部分的最值和后半部分的最值做个比较相当于求整个大数组的最值
    return 最值(left, right);
}

int dp(int arr[], 某状态) {    // 版本二
    for 选择 in [选择列表]
        res = 最值(res, dp(arr, 某状态));
    return res
}

因为位置的原因前序位置的代码只能从函数参数中获取父节点传递来的数据而后序位置的代码不仅可以获取参数数据还可以获取到子树通过函数返回值传递回来的数据。

一旦发现问题和子树有关我们用后序位置 + 给函数设置返回值可以简化代码。