(一) 线性结构的递归模型
链表是一种天然带有递归性质的结构,当我们想要处理 \(Node_A\) 为首的链表,我们尝试处理 \(Node_B\) 为首的链表,然后再单独处理节点 \(A\),类似的,对以 \(Node_B\) 为首的链表我们可以尝试处理 \(Node_C\) 为首的链表,然后再单独处理节点 \(B\),以此类推。当走到末尾空节点的时候,我们返回,逐层的弹出函数的栈帧。
只不过链表是一种线性结构,通常使用循环的方式也可以很容易地实现相关的算法,然而若能在链表一节中打下坚实的基础,在学习树结构的递归模型的会变得非常顺手。 不妨先来回忆一下线性递归模型在链表结构中的几个场景应用,例如打印一个链表、反转一个链表等操作。我们以打印链表为例,我们给出两段非常简短的代码,出于简便,代码中我们使用-1代表空节点,数字 1/2/3/4 分别代表 A/B/C/D,对于链表 \(A \to B\to C \to D\),函数 \(f_1\)、\(f_2\) 会分别打印 \(\{A,B,C,D\}\) 与 \(\{D,C,B,A\}\)。
int list[5] = {1, 2, 3, 4, -1};
void f1(int *list){
if (*list == -1)
return;
printf("%c ", *list + 'A' - 1); // 代码主体逻辑写在递归函数之前
f1(list + 1); // 递归函数
}//最终打印:A B C D
void f2(int *list){
if (*list == -1)
return;
f2(list + 1); // 递归函数
printf("%c ", *list + 'A' - 1); // 代码主体逻辑写在递归函数之后
}//最终打印:D C B A
其中前者称为前序遍历,是指函数递归之前就执行代码的主体逻辑,后者称为后序遍历,是指函数递归之后才执行代码的主体逻辑。前序与后序两种遍历方式,不仅适用于线性结构,其同样适用于树结构。
(二) 二叉树带根树模型
二叉树带根树,是指每个节点只有不大于两个孩子且给定一个指定的根节点的树结构,LeetCode 平台上面绝大部分的树型结构问题均是给定二叉树带根树。