零 题目：算法（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 历史文章 - 总览
2 博主简介
码农三少 ，一个致力于编写 极简、但齐全题解（算法） 的博主。
专一于 一题多解、结构化思维 ，欢送一起刷穿 LeetCode ~