235. 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 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).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
题目链接
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
方法思路
Approach1:
class Solution {
//Runtime: 4 ms, faster than 100.00%
//Memory Usage: 35.1 MB, less than 34.41%
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(find(p, q.val)) return p;
if(find(q, p.val)) return q;
while(root != null){
if((root.val > p.val && root.val < q.val) ||
(root.val < p.val && root.val > q.val))
break;
if(root.val > p.val && root.val > q.val){
root = root.left;
continue;
}
if(root.val < p.val && root.val < q.val)
root = root.right;
}
return root;
}
public boolean find(TreeNode root, int val){
if(root == null) return false;
while(root != null){
if(root.val == val) return true;
if(root.val > val)
root = root.left;
else
root = root.right;
}
return false;
}
}
Approach2:recursive
class Solution {
//Runtime: 4 ms, faster than 100.00%
//Memory Usage: 35.8 MB, less than 5.11%
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Value of current node or parent node.
int parentVal = root.val;
// Value of p
int pVal = p.val;
// Value of q;
int qVal = q.val;
if (pVal > parentVal && qVal > parentVal) {
// If both p and q are greater than parent
return lowestCommonAncestor(root.right, p, q);
} else if (pVal < parentVal && qVal < parentVal) {
// If both p and q are lesser than parent
return lowestCommonAncestor(root.left, p, q);
} else {
// We have found the split point, i.e. the LCA node.
return root;
}
}
}
Approach3: iterative, 思路和方法二一样
class Solution {
//Runtime: 4 ms, faster than 100.00%
//Memory Usage: 35.2 MB, less than 27.21%
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// Value of p
int pVal = p.val;
// Value of q;
int qVal = q.val;
// Start from the root node of the tree
TreeNode node = root;
// Traverse the tree
while (node != null) {
// Value of ancestor/parent node.
int parentVal = node.val;
if (pVal > parentVal && qVal > parentVal) {
// If both p and q are greater than parent
node = node.right;
} else if (pVal < parentVal && qVal < parentVal) {
// If both p and q are lesser than parent
node = node.left;
} else {
// We have found the split point, i.e. the LCA node.
return node;
}
}
return null;
}
}