LeetCode 235. 二叉搜索树的最近公共祖先

Stella981
• 阅读 598

原文链接: LeetCode 235. 二叉搜索树的最近公共祖先

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

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 

我们来复习一下二叉搜索树(BST)的性质:

节点 NN 左子树上的所有节点的值都小于等于节点 NN 的值
节点 NN 右子树上的所有节点的值都大于等于节点 NN 的值
左子树和右子树也都是 BST 

算法

从根节点开始遍历树
如果节点 pp 和节点 qq 都在右子树上,那么以右孩子为根节点继续 1 的操作
如果节点 pp 和节点 qq 都在左子树上,那么以左孩子为根节点继续 1 的操作
如果条件 2 和条件 3 都不成立,这就意味着我们已经找到节 pp 和节点 qq 的 LCA 了

/**
 * 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 (p.val < root.val && q.val < root.val)
    return lowestCommonAncestor(root.left, p, q)
  else if (p.val > root.val && q.val > root.val)
    return lowestCommonAncestor(root.right, p, q)
  return root

};
点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
PTA 是否同一棵二叉搜索树(25 分)
是否同一棵二叉搜索树(25 分)给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2,1,3}和{2,3,1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。输入格式:输入包含若干组测
Kubrnete Kubrnete
3年前
二叉树题集(持续更新中)
对于二叉搜索树,我们规定任一结点的左子树仅包含严格小于该结点的键值,而其右子树包含大于或等于该结点的键值。1\.求二叉搜索树最大深度输入格式:输入给出一行整数序列作为二叉搜索树的键值,数字间以空格分隔,输入0结束(0不计入该二叉树键值)。输入样例:8685109110输出样例:4常规的求二叉搜索树深度的做法是递
似梦清欢 似梦清欢
1年前
树与二叉树
二叉树层次建树二叉树(BinaryTree)是由有限个结点组成的集合,它或者为空集合,或者仅含一个根结点,或者由一个根结点和两棵互不相交的左、右子树组成。树为空即根节点为空。二叉树的基本形态如下图:a:空的二叉树,treeNULL。b:只有空节点的二叉树,
Wesley13 Wesley13
3年前
Java实现 LeetCode 814 二叉树剪枝 (遍历树)
814\.二叉树剪枝给定二叉树根结点root,此外树的每个结点的值要么是0,要么是1。返回移除了所有不包含1的子树的原二叉树。(节点X的子树为X本身,以及所有X的后代。)示例1:输入:\1,null,0,0,1\输出:\1,null,0,null,1\解释:
Stella981 Stella981
3年前
LeetCode(98): 验证二叉搜索树
Medium!题目描述:给定一个二叉树,判断其是否是一个有效的二叉搜索树。一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。示例 1:输入:2/\
Wesley13 Wesley13
3年前
PHP数据结构与算法:二叉树
一、定义二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(leftsubtree)和“右子树”(rightsubtree)。二、特性1.在二叉树的第i层上至多有2^(i1)个结点(i0)2.深度为k的二叉树至多有2^k1个结点(k0)3.对于任意一棵二叉树,如果其叶结点数为N0,而
Stella981 Stella981
3年前
LeetCode(110):平衡二叉树
Easy!题目描述:给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树_每个节点_的左右两个子树的高度差的绝对值不超过1。示例1:给定二叉树 3,9,20,null,null,15,73/\920/
Stella981 Stella981
3年前
LeetCode初级算法之树:98 验证二叉搜索树
01题目信息题目地址:https://leetcodecn.com/problems/validatebinarysearchtree/给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。
Wesley13 Wesley13
3年前
98. 验证二叉搜索树
题目描述给定一个二叉树,判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。输入:5/\14 /\ 
Stella981 Stella981
3年前
LCA最近公共祖先(Tarjan离线算法)
这篇博客对Tarjan算法的原理和过程模拟的很详细。转载大佬的博客https://www.cnblogs.com/JVxie/p/4854719.html(https://www.oschina.net/action/GoToLink?urlhttps%3A%2F%2Fwww.cnblogs.com%2FJVxie%2Fp%2F4854