mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
32 lines
1.2 KiB
Markdown
32 lines
1.2 KiB
Markdown
# [235. Lowest Common Ancestor of a Binary Search Tree](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/)
|
||
# 思路
|
||
求一棵搜索树(BST)中两个节点的最低公共祖先( lowest common ancestor, LCA).
|
||
求二叉树中节点的最低公共祖先比较麻烦(要用到非递归的后序遍历算法)，但是这里是搜索树，由于搜索树中的节点是排好序的，所以这题就简单了。
|
||
若有前提p < q, 那么一共有三种情况:
|
||
* 若p > root, 说明LCA应该在root的右子树内;
|
||
* 若q < root, 说明LCA应该在root的左子树内;
|
||
* 否则，即 p < root < q, 那么root就是LCA。(递归出口)
|
||
|
||
由此可见很容易写出一个递归算法。不过也可以很容易用while循环实现，见下面的代码。
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
|
||
TreeNode *tmp;
|
||
if(p -> val > q -> val){ // 保证 p -> val <= q -> val
|
||
tmp = q;
|
||
q = p;
|
||
p = tmp;
|
||
}
|
||
tmp = root;
|
||
while(tmp){
|
||
if(p -> val > tmp -> val) tmp = tmp -> right;
|
||
else if(q -> val < tmp -> val) tmp = tmp -> left;
|
||
else return tmp;
|
||
}
|
||
}
|
||
};
|
||
```
|