Самый низкий общий предок двоичного кода дерева поиска не принимался

Question

Вопрос: Учитывая двоичное дерево поиска (BST), найдите наименьшего общего предка (LCA) двух заданных узлов в BST.

В соответствии с определением LCA в Википедии: «Самый низкий общий предок определяется между двумя узлами v и w как наименьший узел в T, который имеет как v, так и w как потомки (где мы разрешаем узлу быть потомком само по себе). «

---

Я попытался написать два способа решения проблемы. Второй принимается, но я не понимаю, почему первый ошибается.

коды являются следующие:

1:

public class Solution { 
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) { 
    int max = Math.max(p.val, q.val); 
    int min = Math.min(p.val, q.val); 
    while(max<root.val) { 
     root=root.left; 
    }  
    while (min>root.val) { 
     root=root.right; 
    }  
    return root; 
} 
} 

2:

public class Solution { 
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
    int max = Math.max(p.val, q.val); 
    int min = Math.min(p.val, q.val); 
    while (max<root.val||min>root.val) { 
     root=root.val<min?root.right:root.left; 
    }  
    return root; 
} 
} 

Есть ли разница, если я разделить время цикла? Благодаря!

Answer 1

Вот модифицированный код, основанный на ваш первый один

public class Solution { 
public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q) { 
    int max = Math.max(p.val, q.val); 
    int min = Math.min(p.val, q.val); 
    while (max<root.val&&min>root.val) { 
    root=root.val<min?root.right:root.left; 
    } 
    while(max<root.val) { 
     root=root.left; 
    }  
    while (min>root.val) { 
     root=root.right; 
    }  
    return root; 
} 
} 

Answer 2

Причина заключается в том, что первая попытка только идет сразу после того, как это делается идущую влево, что означает любой целевой узел, который идет вправо, а затем может слева» t достигнута.

Например:

 
     3 
2   8 
     6 
     5 7 
     4 

В приведенном выше дереве, наименьший общий предок 4 и 7: 6, но это не может быть достигнуто.