Dado un árbol binario, encuentre el ancestro común más bajo (LCA) de dos nodos dados en el árbol.
Solución Java 1
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root==null) return null; if(root==p || root==q) return root; TreeNode l = lowestCommonAncestor(root.left, p, q); TreeNode r = lowestCommonAncestor(root.right, p, q); if(l!=null&&r!=null){ return root; }else if(l==null&&r==null){ return null; }else{ return l==null?r:l; } } |
Para calcular la complejidad del tiempo, sabemos que f (n) = 2 * f (n-1) = 2 * 2 * f (n-2) = 2 ^ (logn), entonces tiempo = O (n).
Solución Java 2
class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { CounterNode n = helper(root, p, q); return n.node; } public CounterNode helper(TreeNode root, TreeNode p, TreeNode q){ if(root==null){ return new CounterNode(null, 0); } CounterNode left = helper(root.left, p, q); if(left.count==2){ return left; } CounterNode right = helper(root.right, p, q); if(right.count==2){ return right; } int c=left.count+right.count+(root==p?1:0)+(root==q?1:0); return new CounterNode(root, c); } } class CounterNode{ public int count; public TreeNode node; public CounterNode(TreeNode node, int count){ this.count=count; this.node=node; } } |