【刷算法】LeetCode.236-二叉树的最近公共祖先

Joonas 发布于2019-08-23 14:31 / 3278人阅读

摘要：给定一个二叉树找到该树中两个指定节点的最近公共祖先。示例输入输出解释节点和节点的最近公共祖先是节点。说明所有节点的值都是唯一的。

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

示例 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。因为根据定义最近公共祖先节点可以为节点本身。
 

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

/**
 * 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(r, a, b) {
  if(r === null || r === a || r === b)
    return r;
  
  let left = lowestCommonAncestor(r.left, a, b);
  let right = lowestCommonAncestor(r.right, a, b);
  
  if(left !== null && right !== null) 
    return r;
  
  return left !== null ? left : right;
};

海外云主机 GPU服务器二叉树的遍历二叉树的存储二叉树的存储结构 java二叉树的构建

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/100741.html

前端也需要好好的精进自己的算法

摘要：算法前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。算法前端发展的再快，也不要忘记精进自己的算法，算法是灵魂和核心。我会把我刷过的算法题总结归类，不断完善。欢迎大家关注。数组和堆栈数组去重旋转数组如何快速找出两个数之和等于某一个值的两个数？快排排序算法大总结快速找到数组中的最大值多维数组的展开二分查找有效的括...

hersion 2019-08-23 10:36 评论0 收藏0
Javacript二叉树常见算法实现及快速排序求第K大值

摘要：后面也写了几种常见的排序算法，并用快排求第大值，另外如果之前版的作者看到的话可以留言，我会标明文章引用。之前实习笔试的时候刷题一直用的java，也参考某篇文章写过java版的二叉树常见算法，因为马上要转正面试了，这几天都在准备面试，就把之前的翻出来用javascript重新写了一遍，二叉树基本都是递归处理的，也比较简单，就当做热身。后面也写了几种常见的排序算法，并用快排求第K大值，另...

leeon 2019-08-26 12:15 评论0 收藏0
PHP面试：说说你理解的二叉树吧

摘要：每个节点都必须满足这个属性，这就是二叉搜索树。自平衡二叉树自平衡二叉搜索树或高度平衡二叉搜索树是一种特殊类型的二叉搜索树，它试图通过自动调整来尽量保持树的高度或层次尽可能小。自平衡或高度平衡二叉搜索树有不同的实现。理解和实现树迄今为止，我们对数据结构的探索仅触及线性部分。无论我们使用数组、链表、栈还是队列，都是线性数据结构。我们已经看到了线性数据结构操作的复杂性，大多数时候，插入和...

leejan97 2019-07-01 10:20 评论0 收藏0