Leet Code OJ 235. Lowest Common Ancestor of a Binary Search Tree [Difficulty: Easy]

タイトル:Given a binary search tree(BST)、find the lowest common ancestor(LCA)of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).” For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
原文:検索ツリーを1つ与え、与えられた2つのノードの最小共通祖先(LCA)を見つける.WikipediaのLCAの定義によると、最小共通の祖先はツリーTに定義された最小ノードであり、この最小ノードは満たされ、ツリー上の他の2つのノードvとwはその子孫である(ここでは1つが自分の子孫であることを許可する).例えば上図の2と8のLCAは6、2と4のLCAは2です.
分析:この問題の構想はルートノードという共通の祖先のノードから始まり、二叉樹を検索する性質、すなわちいずれかのノードの左サブツリーのすべてのノードの値が必ずそのノードより小さく、右サブツリーは必ずそのノードより大きく、一歩一歩最小の共通の祖先を見つけることである.あるノードに遍歴すると、2本の木の値はそのノードよりも小さくもなく、そのノードよりも大きくもなく、2つの可能性しかありません.1つ目は2本の木の値で、1つはそのノードより大きく、1つはそのノードより小さい可能性があります.少なくとも1つのサブツリーの値がノードに等しい場合もあります.いずれの可能性も、この時点で最小の共通祖先はこのノードである.
コード:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode LCA=root;
        while(true){
            if(p.val<LCA.val&&q.val<LCA.val){
                LCA=LCA.left;
            }else if(p.val>LCA.val&&q.val>LCA.val){
                LCA=LCA.right;
            }else{
                break;
            }
        }
        return LCA;
    }
}