零题目：算法（leetcode，附思维导图+全解）300题（236）最接近二叉树的publicofAncestors1.题目描述2.概述解决方案（思维导图）3.所有解决方案1??Scheme11)Code://Scheme1"Self.Recursion-storeallpaths".//思路：//1)状态初始化：resList=[],curPpath=[];.//2)调用递归函数。//3)核心：从下往上寻找p和q的共同祖先。varlowestCommonAncestor=function(curRoot,p,q){//递归函数vardfs=function(curPath,curRroot){const{left,right}=curRroot;curPath.push(curRroot);//1)递归退出。if(left===null&&right===null){resList.push(curPath.slice());返回;}//2)递归主体。如果（左===null&&右！==null）{dfs（curPath，右）；curPath.pop();}elseif(left!==null&&right===null){dfs(curPath,left);curPath.pop();}else{dfs(curPath,left);curPath.pop();dfs（curPath，右）；curPath.pop();}}//1)状态初始化：resList=[],curPpath=[];.让resList=[],curPath=[];//2)调用递归函数。dfs(curPath,curRoot);//3)核心：从下往上寻找p和q的共同祖先。让p_path=resList.filter(item=>item.includes(p))[0],q_path=resList.filter(item=>item.includes(q))[0];for(leti=p_path.indexOf(p);i>=0;i--){if(q_path.slice(0,q_path.indexOf(q)+1).includes(p_path[i])){返回p_path[i];}}};2方案21)代码：//方案2“递归法”。//参考：//1)https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2///思路：//1)状态初始化：resNode=null;.//2)调用递归函数dfs(root,p,q);.//3)返回结果resNode.varlowestCommonAncestor=function(root,p,q){constdfs=(curRoot,p,q)=>{//1)递归退出。如果（curRoot==null）{返回假；}//2)递归主体。让inCurrentNode=curRoot===p||curRoot===q,inLeft=dfs(curRoot.left,p,q),inRight=dfs(curRoot.right,p,q);if((inLeft&&inRight)||(inCurrentNode)){resNode=curRoot;}返回左||在右||在当前节点；}//1)状态初始化：resNode=null;.让resNode=null;//2)调用递归函数dfs(root,p,q);.dfs(根,p,q);//3)返回结果resNode.returnresNode;};3Scheme31)Code://Scheme3"Storeparentnodemethod".//参考：//1)https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2///TODO：用手重新撕开。//思路：//1)状态初始化：resParentMap=newMap(),visitedSet=newSet()。//2)调用递归函数dfs(root);.//3）核心处理：暂时省略（TODO）。varlowestCommonAncestor=function(root,p,q){constdfs=(curRroot=null)=>{const{left,right}=curRroot;if(left!==null){resParentMap.set(left.val,curRroot);dfs（左）；}if(right!==null){resParentMap.set(right.val,curRroot);dfs（右）；}};//1)状态初始化：resParentMap=newMap(),visitedSet=newSet().让resParentMap=newMap(),visitedSet=newSet();//2)调用递归函数dfs(root);.dfs（根）；//3）核心处理：暂时省略（TODO）。while(p!=null){visitedSet.add(p.val);p=resParentMap.get(p.val);}while(q!=null){if(visitedSet.has(q.val)){returnq;}q=resParentMap.get(q.val);}}四资源共享&更多1历史文章-概览2博主简介码农三少，一位致力于编写极简但完整的问题解决方案（算法）的博主。专注一题多解，结构化思维，欢迎一起刷LeetCode~
