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

逃离我推掉我的手 2022-08-05 11:15 160阅读 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 条评论，160人围观）

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

相关阅读

相关 LeetCode 235. Lowest Common Ancestor of a Binary Search Tree (Java版; Easy)

[welcome to my blog][] LeetCode Top Interview Questions 235. Lowest Common Ancestor

Dear 丶/ 2023年07月03日 06:14/ 0 赞/ 16 阅读

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

ゝ一世哀愁。/ 2023年07月03日 03:19/ 0 赞/ 21 阅读

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

红太狼/ 2023年07月03日 03:16/ 0 赞/ 21 阅读

相关图解LeetCode236：Lowest Common Ancestor of a Binary Tree

文章目录如何确定两个节点的公共节点？代码实现总结二叉树最低公共祖先节点又是一

逃离我推掉我的手/ 2023年06月15日 11:25/ 0 赞/ 1 阅读

相关 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 赞/ 159 阅读

相关【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 赞/ 161 阅读

相关 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 赞/ 179 阅读

相关 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 赞/ 140 阅读

相关 [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 赞/ 147 阅读

相关 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 赞/ 233 阅读