Самый низкий общий предк в двоичном дереве. Превышен лимит времени

Question

Я написал это решение для поиска LCA двоичного дерева. Он дает ограничение по времени на больших входах. Может кто-то укажет на проблему в этом фрагменте кода. Эта проблема связана с Leetcode OJ.

public class Solution { 
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
    if(root == null){ 
     return null; 
    }if((p.val == root.val) || (q.val == root.val)){ 
     return root; 
    } 
    if(root.left == null && root.right == null){ 
     return null; 
    } 
    boolean leftChildP = isLeftChild(root,p); 
    boolean leftChildQ = isLeftChild(root,q); 

    if(isRightChild(root,p) && isLeftChild(root,q)){ 
     return root; 
    }if(isRightChild(root,q) && isLeftChild(root,p)){ 
     return root; 
    } 
    if(leftChildP && leftChildQ){ 
      return lowestCommonAncestor(root.left,p,q); 
    } 
    return lowestCommonAncestor(root.right,p,q);} 


private boolean isLeftChild(TreeNode root, TreeNode node){ 
    return isChild(root.left,node); 
} 


private boolean isRightChild(TreeNode root, TreeNode node){ 
    return isChild(root.right,node); 
} 


private boolean isChild(TreeNode parent, TreeNode child){ 
    if(parent == null){ 
     return false;} 
    if(parent.val == child.val){ 
     return true; 
    }return (isChild(parent.left,child) || isChild(parent.right,child)); 
}} 

Answer 1

Код, который вы написали имеет сложность O (N^2).

Вы можете найти LCA в O (N) двумя способами

1.) корневой магазин к узлу путь (в ArrayList или может использовать HashSet) для обоих узлов (р, д). Теперь начните сравнивать узлы в обоих путях, начиная с корня (путь до LCA должен совпадать как для p, так и для q), поэтому узел перед тем, когда несоответствие происходит на путях, будет LCA. Это решение должно работать в O (n).

2.) Другое решение работает при допущении, что если только один узел из p и q выходит из вашего дерева, то ваша функция lca вернет этот узел. Вот код, который вы можете сделать

public BinaryTreeNode<Integer> lca(BinaryTreeNode<Integer> root, int data1, int data2){ if(root == null){ return null; } if(root.data == data1 || root.data == data2){ return root; } BinaryTreeNode<Integer> leftAns = lca(root.left, data1 , data2); BinaryTreeNode<Integer> rightAns = lca(root.left, data1 , data2); / // If you are able to find one node in left and the other in right then root is LCA if(leftAns!= null && rightAns != null){ return root; } if(leftAns!=null){ return leftAns; } else{ return rightAns; } }

Это также имеет временную сложность O (п)

Answer 2

рекурсивного lowestCommonAncestor зовёт рекурсивного isChild ... Очень краткий анализ показывает, что это O (N^2). Это займет много времени ...

Попробуйте создать хэшет всех предков p - это может стоить вам O (n), но обычно O (logn). Затем перейдите от q в поисках общего предка. Предполагая, что поиск в hashset стоит O (1), это будет стоить вам снова - O (n), но обычно O (logn).

Вы будете в конечном итоге с типичной сложностью O (LOGN) - что лучше ...