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 236 -- 二叉树的最近公共祖先 ( Lowest Common Ancestor of a Binary Tree ) ( C语言版 )
-
LeetCode 235--二叉搜索树的最近公共祖先 ( Lowest Common Ancestor of a Binary Search Tree ) ( C语言版 )
-
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树
-
235. Lowest Common Ancestor of a Binary Search Tree
-
235. Lowest Common Ancestor of a Binary Search Tree
-
[Leetcode] 235. Lowest Common Ancestor of a Binary Search Tree
-
leetcode 235. Lowest Common Ancestor of a Binary Search Tree(二叉树的最低共同祖先)
-
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree
-
LeetCode 235. Lowest Common Ancestor of a Binary Search Tree C++
-
Leetcode 235. Lowest Common Ancestor of a Binary Search Tree