四刷 08/2022
Version #2 Search on BST
Time O(H) - general O(logN) - O(N)
Space O(1)
Runtime: 7 ms, faster than 64.36% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 50.8 MB, less than 6.63% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (p.val > q.val) {
return lowestCommonAncestor(root, q, p);
}
// p.val <= q.val
while (root != null) {
if (p.val <= root.val && q.val >= root.val) {
return root;
}
if (p.val < root.val) {
root = root.left;
} else {
root = root.right;
}
}
return null;
}
}
三刷 05/2022
还是没有利用到BST的条件
重写
Version #1 General tree solution
Runtime: 10 ms, faster than 14.64% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 51.5 MB, less than 6.51% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
class ResultType {
public int targetCount;
public TreeNode ancestor;
public ResultType() {}
public ResultType(int targetCount, TreeNode ancestor) {
this.targetCount = targetCount;
this.ancestor = ancestor;
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
ResultType result = helper(root, p, q);
return result.ancestor;
}
private ResultType helper(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) {
return new ResultType();
}
ResultType left = helper(node.left, p, q);
if (left.targetCount == 2) {
return left;
}
ResultType right = helper(node.right, p, q);
if (right.targetCount == 2) {
return right;
}
int count = left.targetCount + right.targetCount;
if (node == p || node == q) {
count++;
}
if (count == 2) {
return new ResultType(count, node);
}
return new ResultType(count, null);
}
}
Version #2 Binary Search on BST
Runtime: 9 ms, faster than 26.89% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
Memory Usage: 50.8 MB, less than 6.51% of Java online submissions for Lowest Common Ancestor of a Binary Search Tree.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while (root != null) {
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;
continue;
}
return root;
}
return null;
}
}
竟然没有一刷写的好。。。。。。
还是看一刷的答案好了
60.84 %
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) return null;
if (p.val < q.val) return lowestCommonAncestorHelper(root, p.val, q.val);
else return lowestCommonAncestorHelper(root, q.val, p.val);
}
private TreeNode lowestCommonAncestorHelper(TreeNode root, int small, int large) {
if (root.val >= small && root.val <= large) return root;
else if (root.val < small) return lowestCommonAncestorHelper(root.right, small, large);
else return lowestCommonAncestorHelper(root.left, small, large);
}
}
一刷
这道题在LCA的基础上给了BST的条件
所以判断方法可以是自上而下的
不需要recursion到leaf
When we are traversing from root to its subtrees, the first node ensures that p and q are in the different subtrees is the LCA node.
If both of the targets are larger than our current node, we should look for such LCA in its right subtree. Otherwise we should look for it in its left subtree.
60.84 %
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || p == null || q == null) return null;
if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}
No comments:
Post a Comment