﻿ LeetCode 235 Lowest Common Ancestor of a Binary Search Tree（二-C 语言_软件编程-脚本宝典

# LeetCode 235 Lowest Common Ancestor of a Binary Search Tree（二

## 翻译

``````给定一个二叉搜索树（BST），找出两个给定节点的最小公共祖先（LCA）。

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

## 原文

``````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.``````

## 分析

``````TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == p || root == q) return root;
if (root == NULL || p == NULL || q == NULL) return NULL;

if (p->val < root->val && q->val < root->val) {
return  lowestCommonAncestor(root->left, p, q);
}
else if (p->val > root->val && q->val >root->val) {
return  lowestCommonAncestor(root->right, p, q);
}
return  root;
}``````

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

## 代码

``````/**
* 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 == p || root == q) return root;
if (root == NULL || p == NULL || q == NULL) return NULL;

if (p->val < root->val && q->val < root->val) {
return  lowestCommonAncestor(root->left, p, q);
}
else if (p->val > root->val && q->val >root->val) {
return  lowestCommonAncestor(root->right, p, q);
}
return  root;
}
};``````

Tags：

﻿
<