Sword finger offer 68 - I. nearest common ancestor of binary search tree

The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree

subject

  Given a binary search tree , Find the nearest common ancestor of the two specified nodes in the tree . In Baidu Encyclopedia, the most recent definition of public ancestor is ：“ For a tree T Two nodes of p、q, Recently, the common ancestor is represented as a node x, Satisfy x yes p、q Our ancestors and x As deep as possible （ A node can also be its own ancestor ）.”

Ideas

• When p,q All in root In the right subtree , The traverse root.right
• When p,q All in root The left subtree , The traverse root.left
• When p,q stay root Both sides , It means that we have found the nearest common ancestor

Code

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
class Solution {
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    
        
        while(root != null)
        {
    
            if(root.val < p.val && root.val < q.val)
            {
    
                //  Byte point ratio root It's worth less   explain pq In the left sub tree   Traverse left subtree 
                root = root.right;
            }
            else if(root.val > p.val && root.val > q.val)
            {
    
                root = root.left;
            }
            else{
    
                break;// p q stay root Left and right   explain root The most recent public ancestor   Direct jump out 
            }
        }

        return root;
    }
}