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
|
import java.lang.*;
import java.util.*;
import node.*;
class LowestCommonAncestor {
public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null)
return null;
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);
return root;
}
public static void main(String[] args) {
TreeNode leftLeaf = new TreeNode(0);
TreeNode lMiddleLeaf = new TreeNode(3);
TreeNode rMiddleLeaf = new TreeNode(5);
TreeNode lRightLeaf = new TreeNode(7);
TreeNode rRightLeaf = new TreeNode(9);
TreeNode lowerLeftParent = new TreeNode(4, lMiddleLeaf, rMiddleLeaf);
TreeNode leftParent = new TreeNode(2, leftLeaf, lowerLeftParent);
TreeNode rightParent = new TreeNode(8, lRightLeaf, rRightLeaf);
TreeNode root = new TreeNode(6, leftParent, rightParent);
System.out.println(lowestCommonAncestor(root, leftLeaf, lowerLeftParent).val);
}
}
|
