前言🌧️
算法，对前端人来说陌生又熟悉，很多时候我们都不会像后端工程师一样重视这项能力。但事实上，算法对每一个程序员来说，都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。
当然，学习也是有侧重点的，作为前端我们不需要像后端开发一样对算法全盘掌握，有些比较偏、不实用的类型和解法，只要稍做了解即可。
题目🦀
236. 二叉树的最近公共祖先
难度中等
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：
输入：root = [1,2], p = 1, q = 2 输出：1
提示：
- 树中节点数目在范围
[2, 105]内。 -109 <= Node.val <= 109- 所有
Node.val互不相同。 p != qp和q均存在于给定的二叉树中。
解题思路🌵
- 此题采用回溯算法，而刚好后续遍历就是回溯
- 判断当前结点是否找到了p或者q 如果是直接返回root
- 如果没有
- 递归查找当前结点的左结点
- 递归查找当前结点的右结点
- 对比查找左右结点的返回结果
- 如果左右都找到了，那证明当前root为最近的公共祖先
- 只有一个找到了 则直接返回当前结点，因为另一个没有
解题步骤🐂
//大概公式 // 退出条件 //迭代 // 回溯的返回值处理
lowestCommonAncestor函数的作用就是去查找当前函数是否能查找p 、q结点- 如果能找到直接返回
- 找不到返回null
- 根据查找到的结果判断
- 如果左右结点都找到了 返回root
- 如果只有左有值 或者右 则直接返回
源码🔥
/** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {TreeNode} p * @param {TreeNode} q * @return {TreeNode} */ var lowestCommonAncestor = function(root, p, q) { if(!root){ return null } if(root ===p || root === q){ return root } const left = lowestCommonAncestor(root.left,q,p) const right = lowestCommonAncestor(root.right,q,p) if(left && right){ return root } return left ? left : right };
时间复杂度：O(n)
空间复杂度：O(1)
结束语🌞
那么鱼鱼的LeetCode算法篇的「LeetCode」236-二叉树的最近公共祖先⚡️就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。
