【leetcode每日一题】235.Lowest Common Ancestor of a Binary Search Tree

逃离我推掉我的手 2022-08-05 11:15 120阅读 0赞

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

解析：二分搜索树的性质是根节点的值要大于左孩子节点的值，小于右子孩子节点的值。根据这一性质，我们只需判断给定两个节点的值与根节点的大小关系即可。如果两个值都小于根节点的值，则再去左子树继续寻找；如果两个值都大于根节点的值，则再去右子树继续寻找；否则，他们的最近的公共父节点就是根节点。代码如下：

/**
     * 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* isInSameSide(TreeNode* root,TreeNode* p,TreeNode* q){
        if(p->val<root->val && q->val<root->val)
        {
            root=root->left;
            isInSameSide(root,p,q);
        }
        else if(p->val>root->val && q->val>root->val)
        {
            root=root->right;
            isInSameSide(root,p,q);
        }
        else
            return root;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            return isInSameSide(root,p,q);
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode - Medium - 236. Lowest Common Ancestor of a Binary Tree

Topic Tree Description [https://leetcode.com/problems/lowest-common-ancestor-o

逃离我推掉我的手/ 2022年10月08日 02:30/ 0 赞/ 113 阅读

相关 72【leetcode】经典算法- Lowest Common Ancestor of a Binary Search Tree（lct of bst）

题目描述：一个二叉搜索树，给定两个节点a，b，求最小的公共祖先 _______6______ / \

待我称王封你为后i/ 2022年09月24日 11:29/ 0 赞/ 96 阅读

相关【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

逃离我推掉我的手/ 2022年08月05日 11:15/ 0 赞/ 121 阅读

相关 LeetCode-Lowest Common Ancestor of a Binary Tree 深度解析

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

布满荆棘的人生/ 2022年08月04日 04:10/ 0 赞/ 118 阅读

相关 leetcode 236. Lowest Common Ancestor of a Binary Tree

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

以你之姓@/ 2022年07月25日 16:47/ 0 赞/ 138 阅读

相关 [leetcode]236. Lowest Common Ancestor of a Binary Tree -- JavaScript 代码

/ Definition for a binary tree node. function TreeNode(val) { this.val = val; th

素颜马尾好姑娘i/ 2022年07月17日 01:16/ 0 赞/ 100 阅读

相关 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 nod

落日映苍穹つ/ 2022年07月12日 11:49/ 0 赞/ 90 阅读

相关 [leetcode]: 235. Lowest Common Ancestor of a Binary Search Tree

1.题目 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two g

淡淡的烟草味﹌/ 2022年06月15日 08:10/ 0 赞/ 103 阅读

相关 72【leetcode】经典算法- Lowest Common Ancestor of a Binary Search Tree（lct of bst）

题目描述：一个二叉搜索树，给定两个节点a，b，求最小的公共祖先 _______6______ / \

深藏阁楼爱情的钟/ 2022年04月11日 06:30/ 0 赞/ 118 阅读

相关 236.Lowest Common Ancestor of a Binary Tree

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

刺骨的言语ヽ痛彻心扉/ 2021年10月29日 15:54/ 0 赞/ 190 阅读