【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) {
        List<TreeNode>path_p=findPath(root,p);
        List<TreeNode>path_q=findPath(root,q);
        
        TreeNode ansester=null;//祖先
        //找公共祖先
        for(int i=0;i<path_p.size()&&i<path_q.size();i++){
            if(path_p.get(i)==path_q.get(i))
                ansester=path_p.get(i);
            else
                break;
        }
        return ansester;
    }
    //返回到节点p的路径
    public List<TreeNode> findPath(TreeNode root,TreeNode p){
        List<TreeNode>path=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;
            //当前节点值
            else if(root.val<p.val&&root.val<q.val)
                root=root.right;
            //找打最近公共祖先
            else
                break;
        }
        return root;
    }
}

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

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