# 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 nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

```        _______6______
/              \
___2__          ___8__
/      \        /      \
0      _4       7       9
/  \
3   5```

For example, the lowest common ancestor (LCA) of nodes `2` and `8` is `6`. Another example is LCA of nodes `2` and `4` is `2`, since a node can be a descendant of itself according to the LCA definition.

LCA的算法不唯一，但这里可以运用BST的性质进行搜索，如果p和q在root的一侧，则可以向那一侧搜索，否则root必定为两者的LCA。

```/**
* 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) {
if(!root) return NULL;
while((root->val - p->val) * (root->val - q->val) > 0)
root = root->val > p->val ? root->left : root->right;
return root;
}
};```

0 条评论

• ### Leetcode 104 Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth. The maximum depth is the number o...

• ### Leetcode 98 Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST). Assu...

• ### Leetcode 236. Lowest Common Ancestor of a Binary Tree

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

• ### 776. Split BST

思路： 问题的关键在于进行切分后，树的结构不能改变。影响BST的结构在于输入顺序，所以切分前后，维持输入顺序即可。而BST的层序遍历刚好是最初的输入顺序。所...

• ### 【leetcode刷题】T131-二叉搜索树的最近公共祖先

https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

• ### 剑指offer打卡6：二叉树镜像

在上题中我说了对于与二叉树有关的题目，90% 是采取递归的方式来解决比较简单的。而且解法还都非常相似，没看过上道题的或许可以看一下：剑指offer打卡5：二叉树...

• ### LeetCode 333. 最大 BST 子树（递归）*

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树， 其中最大指的是子树节点数最多的。

• ### 前端慌不慌？用深度学习自动生成HTML代码

大数据技术的应用与发展正在让我们的生活经历一场深刻的“变革”，而且这种变革几乎让所有人都感觉非常舒服，自然而然的就完成了这样的一个变化。最根本的原因其实是大数据...