• Table of Contents
  • 第三周
    • 第 7 课 | 泛型递归、树的递归
      • 递归的实现、特性以及思维要点
      • 实战题目解析
      • 每日一课
    • 第 8 课 | 分治、回溯
      • 分治、回溯的实现和特性
        • 分治
        • 回溯
      • 实战题目解析
    • 作业
      • 中等
    • 下周预习
      • 预习题目

• 递归（Recursion）

  • 递归 - 循环

  • 通过函数体来进行的循环

  • 递归代码模板

    # Python
    def recursion(level, param1, param2, *args):
        # recursion terminator
        if level > MAX_LEVEL:
            process_result
            return
    
        # process logic in current level
        process(level, data, *args)
    
        # drill down
        recursion(level + 1, p1, *args)
    
        # reverse the current level status if needed

    // Java
    public void recur(int level, int param) {
      // terminator
      if (level > MAX_LEVEL) {
        // process result
        return;
      }
      // process current logic
      process(level, param);
      // drill down
      recur( level: level + 1, newParam);
      // restore current status
    
    }

• 思维要点

  1. 不要人肉进行递归（最大误区）
  2. 找到最近最简方法、将其拆解成可重复解决的问题（重复子问题）
  3. 数学归纳法思维

1. 爬楼梯
2. 括号生成
3. 翻转二叉树
4. 验证二叉搜索树
5. 二叉树的最大深度
6. 二叉树的最小深度
7. 二叉树的序列化与反序列化

• 如何优雅地计算斐波那契数列

分治和回溯本质上都是递归，可以把它们认为是递归的一种新的分类

• 分治代码模板

  # Python
  def divide_conquer(problem, param1, param2, ...):
      # recursion terminator
      if problem is None:
        print_result
        return
      # prepare data
      data = prepare_data(problem)
      subproblems = split_problem(problem, data)
      # conquer subproblems
      subresult1 = self.divide_conquer(subproblems[0], p1, ...)
      subresult2 = self.divide_conquer(subproblems[1], p1, ...)
      subresult3 = self.divide_conquer(subproblems[2], p1, ...)
      …
      # process and generate the final result
      result = process_result(subresult1, subresult2, subresult3, …)
  
      # revert the current level states

• 回溯法采用试错的思想，它尝试分布的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，在通过其他的可能的分布解答再次尝试寻找问题的答案。
• 回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：
  1. 找到一个可能存在的正确答案。
  2. 在尝试了所有可能的分布方法后宣告该问题没有答案。 在最坏的情况下，回溯法会导致一次复杂为指数时间的计算。

1. Pow(x, n)
2. 子集
3. 多数元素
4. 电话号码的字母组合
5. N 皇后

1. 二叉树的最近公共祖先 - 题解

    class Solution:
        def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
              if not root or root == p or root == q: return root
              left = self.lowestCommonAncestor(root.left, p, q)
              right = self.lowestCommonAncestor(root.right, p, q)
              if not left and not right: return
              if not left: return right
              if not right: return left
              return root

2. 从前序与中序遍历序列构造二叉树 - 题解

   # Definition for a binary tree node.
   # class TreeNode:
   #     def __init__(self, x):
   #         self.val = x
   #         self.left = None
   #         self.right = None
   
      class Solution:
          def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
              if inorder:
                  root_index = inorder.index(preorder.pop(0))
                  root = TreeNode(inorder[root_index])
                  root.left = self.buildTree(preorder, inorder[:root_index])
                  root.right = self.buildTree(preorder, inorder[root_index + 1:])
                  return root

3. 组合

4. 全排列 - 题解

5. 全排列 II

1. 二叉树的层次遍历
2. 分发饼干
3. 买卖股票的最佳时机 II
4. 跳跃游戏
5. x 的平方根
6. 有效的完全平方数