Categorías
Algorithms

LeetCode: el antepasado común más bajo de un árbol binario (Java)

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;
    }
}
  LeetCode: número de componentes conectados en un gráfico no dirigido (Java)

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *