7、泛型递归、树的递归

07 极客大学-算法训练营-覃超-第七课.pdf

树的解法，一般使用递归

递归

循环
通过函数体调用自己实现循环

mutual exclusive(互斥)
complete exhaustive（完全详尽）

代码模板（补充JS版本的）

https://shimo.im/docs/EICAr9lRPUIPHxsH/read

// JavaScript
const recursion = (level, params) =>{
   // recursion terminator 递归中止条件
   if(level > MAX_LEVEL){
     process_result  // 处理最终的结果
     return; 
   }
  // process current level 处理当前层的逻辑
   process(level, params)
  //drill down 处理下一层的逻辑
   recursion(level+1, params)
  //clean current level status if needed 如果需要处理当前层的状态
}

实战题目

• 爬楼梯（阿里巴巴、腾讯、字节跳动在半年内面试常考）
• 括号生成 (字节跳动在半年内面试中考过)
• 翻转二叉树 (谷歌、字节跳动、Facebook 在半年内面试中考过)
• 验证二叉搜索树（亚马逊、微软、Facebook 在半年内面试中考过）
• 二叉树的最大深度（亚马逊、微软、字节跳动在半年内面试中考过）
• 二叉树的最小深度（Facebook、字节跳动、谷歌在半年内面试中考过）

• 二叉树的序列化与反序列化（Facebook、亚马逊在半年内面试常考）

  课后作业

• 二叉树的最近公共祖先（Facebook 在半年内面试常考）

• 从前序与中序遍历序列构造二叉树（字节跳动、亚马逊、微软在半年内面试中考过）
• 组合（微软、亚马逊、谷歌在半年内面试中考过）
• 全排列（字节跳动在半年内面试常考）
• 全排列 II （亚马逊、字节跳动、Facebook 在半年内面试中考过）

const recursion = ()=>{
    let result = []
  const backtrack = (路径，选择列表)=>{
      if(满足结束条件){
        result.push(结果值)
      return;
    }
    for(选择 in 选择列表){
        做选择
      backtrack(路径，选择列表)
      撤销选择
    }
  }
}