【LeetCode】Day82-二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先【简单】

1. 利用二叉搜索树的性质找到p、q结点，同时记录对应路径path_p和path_q
   （1）如果当前节点值>p值：转向左子树
   （2）如果当前节点值
2. 遍历path_p和path_q，找到最大的 i ，使得path_p[i]==path_q[i]

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Listpath_p=findPath(root,p);
        Listpath_q=findPath(root,q);
        
        TreeNode ansester=null;//祖先
        //找公共祖先
        for(int i=0;i
            if(path_p.get(i)==path_q.get(i))
                ansester=path_p.get(i);
            else
                break;
        }
        return ansester;
    }
    //返回到节点p的路径
    public List findPath(TreeNode root,TreeNode p){
        Listpath=new ArrayList<>();
        while(root!=null){
            path.add(root);
            if(root==p)
                return path;
            else if(root.val>p.val)
                root=root.left;
            else
                root=root.right;
        }
        return path;
    }
}

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( n ) O(n) O(n)

从根节点开始遍历一次，

1. 如果当前节点值>p&q值：转向左子树
2. 如果当前节点值
3. 不满足以上两条，则有两种情况
   （1）p、q分别在当前节点的左右子树中
   （2）当前节点就是p或q
   不管是以上哪种情况，都代表当前节点即为p、q的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
        	//当前节点值>p&q值
            if(root.val>p.val&&root.val>q.val)
                root=root.left;
            //当前节点值 
时间复杂度：
    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)
 
空间复杂度：
    
     
      
       
        O
       
       
        (
       
       
        1
       
       
        )
       
      
      
       O(1)
      
     
    O(1)