专栏首页计算机视觉与深度学习基础Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

Leetcode 235. Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

在二叉搜索树上找出两个点的LCA,最近公共祖先。

LCA的算法不唯一,但这里可以运用BST的性质进行搜索,如果p和q在root的一侧,则可以向那一侧搜索,否则root必定为两者的LCA。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        while((root->val - p->val) * (root->val - q->val) > 0) 
            root = root->val > p->val ? root->left : root->right;
        return root;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 104 Maximum Depth of Binary Tree

    Given a binary tree, find its maximum depth. The maximum depth is the number o...

    triplebee
  • Leetcode 98 Validate Binary Search Tree

    Given a binary tree, determine if it is a valid binary search tree (BST). Assu...

    triplebee
  • Leetcode 236. Lowest Common Ancestor of a Binary Tree

    Given a binary tree, find the lowest common ancestor (LCA) of two given nodes i...

    triplebee
  • 776. Split BST

    思路: 问题的关键在于进行切分后,树的结构不能改变。影响BST的结构在于输入顺序,所以切分前后,维持输入顺序即可。而BST的层序遍历刚好是最初的输入顺序。所...

    用户1147447
  • 【leetcode刷题】T131-二叉搜索树的最近公共祖先

    https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

    木又AI帮
  • 剑指offer打卡6:二叉树镜像

    在上题中我说了对于与二叉树有关的题目,90% 是采取递归的方式来解决比较简单的。而且解法还都非常相似,没看过上道题的或许可以看一下:剑指offer打卡5:二叉树...

    帅地
  • LeetCode 333. 最大 BST 子树(递归)*

    给定一个二叉树,找到其中最大的二叉搜索树(BST)子树, 其中最大指的是子树节点数最多的。

    Michael阿明
  • 前端慌不慌?用深度学习自动生成HTML代码

    机器之心
  • 前端慌不慌?用深度学习自动生成HTML代码

    编程软文
  • 基于DKHadoop的智慧人社服务平台开发案例简述

    大数据技术的应用与发展正在让我们的生活经历一场深刻的“变革”,而且这种变革几乎让所有人都感觉非常舒服,自然而然的就完成了这样的一个变化。最根本的原因其实是大数据...

    IT小白龙

扫码关注云+社区

领取腾讯云代金券