-
Notifications
You must be signed in to change notification settings - Fork 0
/
LowestCommonAncestorofaBinarySearchTree.hpp
52 lines (49 loc) · 1.46 KB
/
LowestCommonAncestorofaBinarySearchTree.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
//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.
#include "Tree.hpp"
/**
* 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 (nullptr == root || nullptr == p || nullptr == q)
return nullptr;
if ((root->val <= p->val && root->val >= q->val)
|| (root->val >= p->val && root->val <= q->val)
)
return root;
else 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);
}
};