欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 235. Lowest Common Ancestor of a Binary Search Tree C++

程序员文章站 2022-07-14 14:11:13
...

Problem

题目链接

Solution

题意为给定一个BST(二叉搜索树)和两个树中的节点p、q,要求你找出p、q节点的最低公共祖先节点。
最低公共祖先节点定义为树中同时有p、q两个后代节点的最低节点,同时,一个节点也可以作为其自身的祖先节点。
题目还规定了1、树中节点所有值不同2、p和q是不同的两个节点且必定存在于树中
有了这两点规定,就不用考虑很多的边界情况了,处理还是比较方便的。基于BST的特性,我们可以知道,如果对于当前节点v,若v的值处于pq值之间,那么pq必定分别位于v的左右子树中,画个简单的示意图就可知道,此时v必定是pq的最低公共祖先;若p与q的值若都大于v的值,那么p与q一定都在v的右子树中,v也一定不是pq的最低公共祖先节点;若p与q的值若都小于v的值,那么p与q一定都在v的左子树中,v也一定不是pq的最低公共祖先节点。
基于上述思想,可以编写代码:

/**
 * 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) {
        int a=p->val;
        int b=q->val;
        if(a>b){
            int t=a;
            a=b;
            b=t;
        }
        while(true){
            if(root->val>=a&&root->val<=b) return root;
            if(root->val>b) root=root->left;
            else if(root->val<a) root=root->right;
        }
        return NULL;
    }
};

Result

LeetCode 235. Lowest Common Ancestor of a Binary Search Tree C++