四刷 05/2022
Version #1 Recursion
Time O(N)
Space O(N)
Runtime: 10 ms, faster than 46.12% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 47.1 MB, less than 52.11% of Java online submissions for Lowest Common Ancestor of a Binary 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) {
TreeNode[] lca = new TreeNode[1];
countTarget(root, p, q, lca);
return lca[0];
}
// Returns how many target nodes are in the subtree
private int countTarget(TreeNode node, TreeNode p, TreeNode q, TreeNode[] lca) {
if (node == null) { // already found
return 0;
}
int left = countTarget(node.left, p, q, lca);
if (left == 2) {
return 2;
}
int right = countTarget(node.right, p, q, lca);
if (right == 2) {
return 2;
}
int count = left + right;
if (node == p || node == q) {
count++;
}
if (count == 2) {
lca[0] = node;
}
return count;
}
}
Version #2 Iteration with BFS
Time O(N)
Space O(N)
Runtime: 22 ms, faster than 7.16% of Java online submissions for Lowest Common Ancestor of a Binary Tree.
Memory Usage: 49.1 MB, less than 7.00% of Java online submissions for Lowest Common Ancestor of a Binary 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) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
Map<TreeNode, TreeNode> parent = new HashMap<>();
// Find all the parent nodes of p and q
Queue<TreeNode> que = new ArrayDeque<>();
que.offer(root);
while (!que.isEmpty() && (!parent.containsKey(p) || !parent.containsKey(q))) {
TreeNode curr = que.poll();
if (curr.left != null) {
parent.put(curr.left, curr);
que.offer(curr.left);
}
if (curr.right != null) {
parent.put(curr.right, curr);
que.offer(curr.right);
}
}
Set<TreeNode> pAncestors = new HashSet<>();
while (p != null) {
pAncestors.add(p);
p = parent.getOrDefault(p, null);
}
while (q != null) {
if (pAncestors.contains(q)) {
return q;
}
q = parent.getOrDefault(q, null);
}
return null;
}
}
感觉还是之前写的好
40.96 %
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return check(root, p, q);
}
// Given a node
// If p == node, return p, if q == node, return q
// If pq in different subtree, return curr node
private TreeNode check(TreeNode node, TreeNode p, TreeNode q) {
if (node == null) {
return null;
}
if (node == p || node == q) {
return node;
}
TreeNode left = check(node.left, p, q);
TreeNode right = check(node.right, p, q);
if (left != null && right != null) {
return node;
} else if (left != null) {
return left;
} else if (right != null) {
return right;
} else {
return null;
}
}
}
二刷
39.72 %
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
}
一刷
15.04 %
/**
* 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 || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) return root;
return left != null ? left : right;
}
}
No comments:
Post a Comment