https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/description/

 

一开始没仔细看题目是搜索树，写的是普通二叉树的解法：

 

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    TreeNode result = null;    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {        findNode(root,p,q);        return result;    }            public int findNode(TreeNode root, TreeNode p, TreeNode q)    {        if(root==null || result !=null) return 0;        int lv = findNode(root.left,p,q);        int rv = findNode(root.right,p,q);        if(result!=null) return 0;        if(root==p)        {            if(lv+rv==2) result = p;            return 1;        }        if(root==q)        {            if(lv+rv==1) result = q;            return 2;        }        if(lv + rv ==3) result = root;        return lv+rv;    }}

 

搜索树就简单很多了：

/** * 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) {        if(root==null) return null;        if(p.val < q.val)        {            if(root.val > q.val) return lowestCommonAncestor(root.left,p,q);            else if(root.val < p.val) return lowestCommonAncestor(root.right,p,q);            else return root;        }        else return lowestCommonAncestor(root,q,p);    }}