递归与回溯算法详解

递归是计算机科学中的核心概念，是许多算法和数据结构的基础。其核心思想是：将问题分解为更小的子问题，直到子问题足够简单可以直接求解。

每个递归函数都需要包含：

基本情况（Base Case）：不使用递归就能直接求解的终止条件
递推关系（Recurrence Relation）：将问题拆分到基本情况的规则

例题

21 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

输入：**l1 = [1,2,4], l2 = [1,3,4] **输出：[1,1,2,3,4,4]

**示例 2：**

**输入：**l1 = [], l2 = []
**输出：**[]

示例 3：

输入：**l1 = [], l2 = [0] **输出：[0]

**提示：**

- 两个链表的节点数目范围是 `[0, 50]`
    - <code>-100 <= Node.val <= 100</code>
    - `l1` 和 `l2` 均按 **非递减顺序** 排列

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    } else if list2 == nil {
        return list1
    } else if list1.Val < list2.Val {
        list1.Next = mergeTwoLists(list1.Next, list2)
        return list1
    } else {
        list2.Next = mergeTwoLists(list1, list2.Next)
        return list2
    }
}

💣 206 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 示例 1：

输入：**head = [1,2,3,4,5] **输出：[5,4,3,2,1]

**示例 2：**

![题目图示](https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg)

**输入：**head = [1,2]
**输出：**[2,1]

示例 3：

输入：**head = [] **输出：[]

**提示：**

- 链表中节点的数目范围是 `[0, 5000]`
    - <code>-5000 <= Node.val <= 5000</code>

**进阶：**链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

700 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2 输出：[2,1,3]

**示例 2:**

![题目图示](https://assets.leetcode.com/uploads/2021/01/12/tree2.jpg)

<b>输入：</b>root = [4,2,7,1,3], val = 5
<b>输出：</b>[]

提示：

数中节点数在 [1, 5000] 范围内
- 1 <= Node.val <= 10^7
- root 是二叉搜索树
- 1 <= val <= 10^7

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func searchBST(root *TreeNode, val int) *TreeNode {
    if root != nil {
        if val == root.Val {
            return root
        } else if val < root.Val {
            return searchBST(root.Left, val)
        } else {
            return searchBST(root.Right, val)
        }
    }
    return nil
}

70 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？