【递归+回溯】

三级地址选择器引出的递归回溯方法

• 题目介绍
• • 题解
  • 回溯模板
  • 拓展（leetcode17、22、46、77、79、78）

题目介绍

已知数据格式，实现一个函数 fn ，给一个 id 找出链条中其对应的所有的父级 name

示例1: 传入 id ddrr2, 返回 广东省深圳市福田区A街道

示例2: 传入 id sdsd, 返回 广东省深圳市

const cityData = [{
 id: 'axzx',
 name: '广东省',
 children: [
   {
     id: 'sdsd',
     name: '深圳市',
     children: [
       {
         id: '45dss',
         name: '南山区'
       },
       {
         id: 'sdsd11',
         name: '福田区',
         children: [{
           id: 'ddrr2',
           name: 'A街道'
         }]
       }
     ]
   },
   {
     id: '2323d',
     name: '东莞市',
     children: [
       {
         id: 'xxs2',
         name: 'A区'
       },
       {
         id: 'kklio2',
         name: 'B区',
       }
     ]
   }
 ]
}];
           

题解

这是三级地址select组件最常用的算法，可以将数组结构看成一棵树，然后用递归+回溯的方法做，首先可以思考递归出口以及每一层递归的函数传参，这道题目递归出口有两种情况：第一种找到了对应的id，第二种情况已经遍历到当前最后一层还没找到。（第一种情况需要结束整个函数并return出结果，第二种情况需要结束当前递归并回到上一层状态）

function search(id,data){
    // 1.递归函数
    function recurse(currentData){
        // 2. 递归出口
        if(currentData?.id===id) return;
        if(!currentData?.children) return;
        for(const v of currentData){
            recurse(v?.children);
        }
        
    }
    for(const v of data){
        recurse(v);  
    }
}
           

根据题意还需要一个res数组在每次递归时将当前遍历对象的name push进去，并且两种递归出口后续操作完全不同，所以在代码中新增一个res并且修改递归出口函数。

function search(id,data){
    let res = [];
    // 1.递归函数
    function recurse(currentData){
        // 2. 递归出口
        if(currentData?.id===id) return true;
        if(!currentData.children) return false;
        for(const v of currentData.children){
            res.push(v.name);
            const flag = recurse(v);
            if(flag){
                return true;
            }
            // 回溯
            res.pop();
        }
        
    }
    for(const v of data){
        res.push(v.name);
        const flag = recurse(v);
        if(flag){
            console.log(res);
            return res.join('');
        }
        // 回溯
        res.pop();
    }
}
           

回溯模板

上述题目中当当前节点无子节点退出当前递归后需要执行回溯算法，回溯算法可以套用下面框架

function main(){
	function curse(){
		/*递归出口*/
		for(){
			/**状态压入*/
			curse();
			/**回溯，状态推出 */
		}
	}
	curse(); 
}
           

拓展（leetcode17、22、46、77、79、78）

leetcode17 链接: 电话号码的字母组合

leetcode22 链接: 括号生成

leetcode46 链接: 全排列

leetcode77 链接: 组合

leetcode78 链接: 子集

leetcode79 链接: 单词搜索

类似题目都可以去根据上述思路来做，先递归到最后一层节点，如果满足题意，那么直接return，如果不满足，回溯到上一节点压入另外的状态继续递归，直到满足题目要求为止。注意递归中每一层的需要遍历哪些数据，比如电话号码字母组合中的需要遍历当前数字的所有字母。

var letterCombinations = function(digits) {
	let matrix = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
	function curse(i){
		/**出口 */
		for(const v of matrix[digits[i]]){
			/**状态压入 */
			curse(i+1);
			/**状态pop*/
		}
	}
	curse(0)
};