236二叉树的最近公共祖先算法（附思维导图全部解法）300题

　　零 标题：算法（leetcode，附思维导图 + 全部解法）300题之（236）二叉树的最近公共祖先
　　一 题目描述
　　二 解法总览（思维导图）
　　思维导图
　　三 全部解法1 方案1
　　1)代码： // 方案1 ＂自己。递归-存储所有路径法＂。  // 思路： // 1）状态初始化：resList = [], curPpath = []; 。 // 2）调用递归函数。 // 3）核心：依次从底下往上找 p、q 的公共祖先。 var lowestCommonAncestor = function(curRoot, p, q) {     // 递归函数     var dfs = function(curPath, curRroot){         const {left, right} = curRroot;         curPath.push(curRroot);                  // 1）递归出口。         if (left === null && right === null) {             resList.push(curPath.slice());             return;         }          // 2）递归主体。         if (left === null && right !== null) {             dfs(curPath, right);             curPath.pop();         }         else if (left !== null && right === null) {             dfs(curPath, left);             curPath.pop();         }         else {             dfs(curPath, left);             curPath.pop();             dfs(curPath, right);             curPath.pop();         }     }      // 1）状态初始化：resList = [], curPpath = []; 。     let resList = [],         curPath = [];      // 2）调用递归函数。     dfs(curPath, curRoot);      // 3）核心：依次从底下往上找 p、q 的公共祖先。     let p_path = resList.filter(item => item.includes(p))[0],         q_path = resList.filter(item => item.includes(q))[0];          for(let i = p_path.indexOf(p); i >= 0; i--){         if(q_path.slice(0, q_path.indexOf(q) + 1).includes(p_path[i])){             return p_path[i];         }     } };
　　2 方案2
　　1)代码： // 方案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 。 var lowestCommonAncestor = function(root, p, q) {     const dfs = (curRoot, p, q) => {         // 1）递归出口。         if(curRoot == null){             return false;         }          // 2）递归主体。         let inCurrentNode = curRoot === p || curRoot === q,             inLeft = dfs(curRoot.left, p, q),             inRight = dfs(curRoot.right, p, q);                  if((inLeft && inRight) || (inCurrentNode)){             resNode = curRoot;         }         return inLeft || inRight || inCurrentNode;     }      // 1）状态初始化：resNode = null; 。     let resNode = null;      // 2）调用递归函数 dfs(root, p, q); 。     dfs(root, p, q);      // 3）返回结果 resNode 。     return resNode; };
　　3 方案3
　　1)代码： // 方案3 ＂存储父节点法＂。 // 参考： // 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 = new Map(), visitedSet = new Set() 。 // 2）调用递归函数 dfs(root); 。 // 3）核心处理：暂略（TODO）。 var lowestCommonAncestor = function(root, p, q) {     const dfs = (curRroot = null) => {         const {left, right} = curRroot;                  if (left !== null) {             resParentMap.set(left.val, curRroot);             dfs(left);         }          if (right !== null) {             resParentMap.set(right.val, curRroot);             dfs(right);         }     };      // 1）状态初始化：resParentMap = new Map(), visitedSet = new Set() 。     let resParentMap = new Map(),         visitedSet = new Set();          // 2）调用递归函数 dfs(root); 。     dfs(root);      // 3）核心处理：暂略（TODO）。     while (p != null) {         visitedSet.add(p.val);         p = resParentMap.get(p.val);     }     while (q != null) {         if (visitedSet.has(q.val)) {             return q;         }         q = resParentMap.get(q.val);     } }
　　四 资源分享 & 更多1 历史文章 - 总览
　　历史文章 - 总览
　　刷题进度 - LeetCode：526 / 2662 、《剑指offer》：66 / 66
　　2 博主简介
　　码农三少 ，一个致力于编写  极简、但齐全题解（算法 ） 的博主。 专注于  一题多解、结构化思维  ，欢迎一起刷穿 LeetCode ~