1644. Lowest Common Ancestor of a Binary Tree II
Last updated
Last updated
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity : O(N), where N is the number of nodes in the binary tree.
* In the worst case we might be visiting all the nodes of the binary tree.
* Space complexity : O(N). This is because the maximum amount of space
* utilized by the recursion stack would be N since the height of a
* skewed binary tree could be N.
*/
class Solution {
private int count = 0;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode lca = lcaHelper(root, p, q);
return (count == 2)? lca: null;
}
private TreeNode lcaHelper(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
TreeNode left = lcaHelper(root.left, p, q);
TreeNode right = lcaHelper(root.right, p, q);
if(root == p || root == q) {
count++;
return root;
}
if(left != null && right != null) {
return root;
}
return (left == null)? right: left;
}
}