-
Notifications
You must be signed in to change notification settings - Fork 0
/
lcaOfBST.cpp
39 lines (34 loc) · 804 Bytes
/
lcaOfBST.cpp
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
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class TreeNode
{
public:
T data;
TreeNode<T> *left;
TreeNode<T> *right;
TreeNode(T data)
{
this->data = data;
left = NULL;
right = NULL;
}
~TreeNode()
{
if (left)
delete left;
if (right)
delete right;
}
};
TreeNode<int> *LCAinaBST(TreeNode<int> *root, TreeNode<int> *p, TreeNode<int> *q)
{
if (p->data > q->data)
return LCAinaBST(root, q, p);
if (p->data <= root->data && q->data >= root->data)
return root;
if (p->data < root->data && q->data < root->data)
return LCAinaBST(root->left, p, q);
if (p->data > root->data && q->data > root->data)
return LCAinaBST(root->right, p, q);
}