二叉搜索树的最近公共祖先

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */

    int cur_val; //记录当前找到的符合要求的节点
    int cur_d = Integer.MAX_VALUE; //记录当前符合要求的节点的深度
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
       returnType res = LCA(root, p, q);
       return cur_val;
    }

    public returnType LCA(TreeNode root, int p, int q){
        //向左右子树索要信息：1.左右子树是否同时包含p，q (所有节点的值都是唯一的)；2. 左右子树当前深度 3. 节点值
        returnType res = new returnType(0, false, false);
        if(root == null) return res;
        returnType l_res = LCA(root.left, p, q);
        returnType r_res = LCA(root.right, p, q);
        res.depth = Math.max(l_res.depth, r_res.depth) + 1; // 计算当前深度
        if(root.val == p || (l_res.has_p || r_res.has_p)) res.has_p = true; //当前/左/右子树包含p
        if(root.val == q || (l_res.has_q || r_res.has_q)) res.has_q = true; //当前/左/右子树包含q
        if(res.has_p && res.has_q && res.depth <= cur_d){ // 要求节点拥有p,q且高度最低，即深度最大
            cur_d = res.depth; //记录当前深度
            cur_val = root.val;
        }
        return res;
    }

    public class returnType{
        int depth = 0;
        boolean has_p = false;
        boolean has_q = false;
        public returnType(int depth, boolean has_p, boolean has_q){
            this.depth = depth;
            this.has_p = has_p;
            this.has_q = has_q;
        }
    }
}

public class Solution {
    /**
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if (null == root) {
            return 0;
        }
        int val = root.val;
        int min = Math.min(p, q);
        int max = Math.max(p, q);
        if (val >= min && val <= max) {
            return val;
        }
        if (val > max) {
            return lowestCommonAncestor(root.left, p, q);
        }
        if (val < min) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return 0;
    }
    
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // 1. 参数校验
        if(root == null) {
            return -1;
        }

        // 2. 利用二叉搜索树的性质
        // 左子树比根节点小,右子树比根节点大
        
        // 3. 判断 p q 分别在根节点的什么位置
        if((p <= root.val && q >= root.val) || (p >= root.val && q <= root.val)) {
            // p q 在 root 的两侧 -> 最近公共祖先就是 root
            return root.val;
        } else if (p <= root.val && q <= root.val) {
            // p q 在 root 的左侧 -> 递归去寻找
            return lowestCommonAncestor(root.left,p,q);
        } else {
            // p q 在 root 的右侧 -> 递归去寻找
            return lowestCommonAncestor(root.right,p,q);
        }
    }
}

 public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // 变化的是root的值，因为寻找的是root
        if(root==null) return -1;
        int min=Math.min(p,q);
        int max=Math.max(p,q);
        int ans=build(root,min,max);
        return ans;
    }
    public int build(TreeNode root,int min,int max){
        if(root==null) return -1;
        if(root.val<min){//root.val太小，应该变大
            return build(root.right,min,max);
        }
        if(root.val>max){
            return build(root.left,min,max);
        }
        return root.val;
    }

public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        TreeNode cur=root;
        while(true){
            //比当前节点小就左移
            if(p<cur.val&&q<cur.val){
                cur=cur.left;
            //比当前节点大就右移
            }else if(p>cur.val&&q>cur.val){
                cur=cur.right;
            //一旦出现一大一小说明节点已经找到
            }else{
                return cur.val;
            }
        }
    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        int commonParentValue = 0;
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        traversal(root, p, l1);
        traversal(root, q, l2);
        int size1 = l1.size();
        int size2 = l2.size();
        int size = Integer.min(size1, size2);
        for (int i = 0; i < size; i++) {
            if (l1.get(i).equals(l2.get(i))) {
                commonParentValue = l1.get(i);
            }
        }
        return commonParentValue;
    }



    private void traversal(TreeNode root, int v, List<Integer> list) {
        if (root == null) {
            return;
        }
        list.add(root.val);
        if (root.val == v) {
            return;
        }

        if (root.val < v) {
            traversal(root.right, v, list);
        } else {
            traversal(root.left, v, list);
        }

    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // p q在当前根的左右侧，直接返回根， 因为无论p 和 q 处于什么位置，它的祖先必然是当前的根
        if((p <= root.val && q >= root.val) || (p >= root.val && q <= root.val))
            return  root.val;
        
        // 两个数在根的左侧  左递归
        if(p < root.val) return  lowestCommonAncestor (root.left, p, q);
        // 否则右递归
        return  lowestCommonAncestor (root.right, p, q);
        
    }
}

public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        //两个数组，用于记录p，q的结点
        LinkedList<Integer> l1 = new LinkedList<>();
        LinkedList<Integer> l2 = new LinkedList<>();
        int ans = 0;

        TreeNode t1 = root;
        TreeNode t2 = root;

        while (t1.val != p) {
            if (t1.val > p) { //走左边
                l1.add(t1.val);
                t1 = t1.left;
            } else { //走右边
                l1.add(t1.val);
                t1 = t1.right;
            }
        }
        l1.add(p);

        while (t2.val != q) {
            if (t2.val > q) { //走左边
                l2.add(t2.val);
                t2 = t2.left;
            } else { //走右边
                l2.add(t2.val);
                t2 = t2.right;
            }
        }
        l2.add(q);

        while (l1.size() != l2.size()) {
            if (l1.size() > l2.size()) {
                l1.removeLast();
            } else {
                l2.removeLast();
            }
        }

        while (l1.getLast() != l2.getLast()) {
            l1.removeLast();
            l2.removeLast();
        }
        ans = l1.getLast();
       

        return ans;

    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        int min  = Math.min(p, q);
        int max = Math.max(p, q);

        //当root.val大于min，同时大于max，则公共祖先节点在左子树
        if (root.val > min && root.val > max)
            return lowestCommonAncestor(root.left, p, q);

        //当root.val大于min，同时大于max，则公共祖先节点在右子树
        if (root.val < min && root.val < max)
            return lowestCommonAncestor(root.right, p, q);

        /**
            只剩下两种情况:
            1.当root.val等于min或者max,则为root.val
            if (root.val == min || root.val == max)
                return root.val;
            2.当root.val小于左边大于右边，则为root.val
            if (root.val > min && root.val < max)
                return root.val;
         */
        return root.val;
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        List<TreeNode> l = order(root,q);
        List<TreeNode> r = order(root,p);
        int last = -1;
        for(int i=0;i<l.size()&&i<r.size();i++){
            if(l.get(i).val==r.get(i).val){
                last = l.get(i).val;
            }
        }
        return last;
    }
    
    
    private List<TreeNode> order(TreeNode root,int p){
        if(null!=root){
            if(root.val == p){
                List<TreeNode> l = new ArrayList();
                l.add(root);
                return l;
            }
            List<TreeNode> lf = order(root.left,p);
            if(null!=lf){
                lf.add(0,root);
                return lf;
            }
             List<TreeNode> rg = order(root.right,p);
             if(null!=rg){
                rg.add(0,root);
                return rg;
             }
        }
        return null;
    }
    
    
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        if (root.val > p && root.val < q) return root.val;
        if (root.val == p || root.val == q) return root.val == q ? q : p;
        if (root.val > p && root.val > q) return lowestCommonAncestor(root.left, p, q);
        return lowestCommonAncestor(root.right, p, q);
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    
    //先将父节点和左右节点的值入hashmap--用于根据左右的值找父节点
    //map和set是全局都要用到的变量 
    Map<Integer,TreeNode> parent=new HashMap<Integer,TreeNode>();
    Set<Integer> visited=new HashSet<Integer>();
    Map<Integer,TreeNode> self=new HashMap<Integer,TreeNode>();
    
    public void dfs(TreeNode root){//放左右的值和父node
        if(root.left!=null){
            parent.put(root.left.val,root);
            dfs(root.left);
        }
        if(root.right!=null){
            parent.put(root.right.val,root);
            dfs(root.right);
        }
    }
    
    public void myself(TreeNode root){//放自己的值和node
        if(root==null){return;}
        self.put(root.val,root);
        if(root.left!=null){myself(root.left);}
        if(root.right!=null){myself(root.right);}
    }
    
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        dfs(root);
        myself(root);
        TreeNode p_node=self.get(p);//找p对应的节点 
        TreeNode q_node=self.get(q);//同理，找q对应的节点
 
        while(p_node!=null){
            visited.add(p_node.val);//将从p出发的所有父节点入set
            p_node=parent.get(p_node.val);
        }
        while(q_node!=null){
            if(visited.contains(q_node.val)){return q_node.val;}//如果q的值在p的父结点中---找到了
            q_node=parent.get(q_node.val);
            
        }
        return root.val;
      
    }
    
    
}

对于所有的二叉树

public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if (root==null) return -1;
        if (root.val==p || root.val==q) return root.val;
        int left = lowestCommonAncestor(root.left, p, q);
        int right = lowestCommonAncestor(root.right, p, q);
        if (left!=-1 && right!=-1) return root.val;
        if (left==-1) return right;
        else return left;
    }

对于二叉搜索树

public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if (root.val<p && root.val<q) {
            return lowestCommonAncestor(root.right,p,q);
        }
        if (root.val>p && root.val>q) {
            return lowestCommonAncestor(root.left,p,q);
        }
        return root.val;
    }