-
Notifications
You must be signed in to change notification settings - Fork 0
/
lowcommonancesstor_leet235.java
32 lines (25 loc) · 1.1 KB
/
lowcommonancesstor_leet235.java
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
// Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.
// According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
// Example 1:
// Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
// Output: 6
// Explanation: The LCA of nodes 2 and 8 is 6.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(p.val==root.val || q.val==root.val)
{
System.out.println("hello");
return root;
}
if((p.val > root.val && q.val < root.val) || (q.val>root.val && p.val<root.val))
return root;
if(p.val>root.val && q.val>root.val)
root=lowestCommonAncestor(root.right,p,q);
if(p.val<root.val && q.val<root.val)
{
System.out.println("hii"+p.val);
root=lowestCommonAncestor(root.left,p,q);
}
return root;
}
}