在二叉树中找到两个节点的最近公共祖先

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 {
    public class Info {
        public boolean findP;
        public boolean findQ;
        public int lowestCommonAncestor;

        public Info () {
            this.findP = false;
            this.findQ = false;
            this.lowestCommonAncestor = -1;
        }

        public Info (boolean findP, boolean findQ, int lowestCommonAncestor) {
            this.findP = findP;
            this.findQ = findQ;
            this.lowestCommonAncestor = lowestCommonAncestor;
        }
    }
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here

        // 根据左程云老师讲的【二叉树递归套路】，先弄明白三件事
        // 1.我要干什么：
        //        获知【左子树】中【有无p，q或最小公共祖先】
        //        获知【右子树】中【有无p，q或最小公共祖先】

        // 2.我需要什么信息：
        //      综上所述，我需要左右子树的【有无p，q或最小公共祖先】

        // 3.我如何利用两个子树的信息加工出来我的信息：
        //      将有无p和q取或；若左右子树已经有lowestCommonAncestor了，则传递，反之则赋值

        // 调用递归函数求解
        return process(root, o1, o2).lowestCommonAncestor;
    }

    public Info process(TreeNode root, int p, int q) {
        // 递归出口
        if (root == null) {
            // 到底返回
            return new Info();
        }

        // 从左右子树获取信息
        Info leftInfo = process(root.left, p, q);
        Info rightInfo = process(root.right, p, q);

        // 根据获取到的信息加工出自己的信息
        // 三者满足其一即可为true
        boolean findP = leftInfo.findP || rightInfo.findP || root.val == p;
        boolean findQ = leftInfo.findQ || rightInfo.findQ || root.val == q;
        if (findP && findQ) {
            // 如果本子树已经同时发现P和Q了
            if (leftInfo.lowestCommonAncestor == -1 && rightInfo.lowestCommonAncestor == -1) {
                // 同时两个子树都不曾同时发现P和Q
                // 说明本结点才是P和Q的最近公共祖先节点
                return new Info(findP, findQ, root.val);
            } else {
                // 同时两个子树中已经有一个找到最近公共祖先节点了
                // 将它们中非-1的那个传递下去
                int val = (leftInfo.lowestCommonAncestor != -1) ? leftInfo.lowestCommonAncestor : rightInfo.lowestCommonAncestor;
                return new Info(findP, findQ, val);
            }
        }
        // 还没同时发现P和Q，将当前状态向上传递
        return new Info(findP, findQ, -1);
    }
}

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 o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        return dfs(root,o1,o2).val;
    }

    private TreeNode dfs(TreeNode root, int o1, int o2) {
        if (root == null) {
            return null;
        }

        if (root.val == o1) {
            return root;
        }
        if (root.val == o2) {
            return root;
        }

        TreeNode left = dfs(root.left, o1, o2);
        TreeNode right = dfs(root.right, o1, o2);
        if(left!=null && right!=null) return root;
        if(left!=null) return left;
        return right;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    int cur_val; // 记录当前符合要求节点的值
    int cur_d = Integer.MAX_VALUE; // 记录符合要求节点的深度/高度
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        LCA(root, o1, o2);
        return cur_val;
    }
    public returnType LCA(TreeNode root, int o1, int o2){
        // 向左右子树索要信息：1. 当前高度 2. 是否同时含有o1,o2
        returnType res = new returnType(0, false, false);
        if(root == null) return res;
        returnType l_res = LCA(root.left, o1, o2);
        returnType r_res = LCA(root.right, o1, o2);
        res.depth = Math.max(l_res.depth, r_res.depth) + 1; // 计算当前高度
        if(root.val == o1 || l_res.has1 || r_res.has1) res.has1 = true; //当前/左右是否含有1
        if(root.val == o2 || l_res.has2 || r_res.has2) res.has2 = true; //当前/左右是否含有2
        if(res.has1 && res.has2 && res.depth <= cur_d){ // 符合要求且最小高度
            cur_d = res.depth; //记录
            cur_val = root.val; // 记录
        }
        return res;
    }
    public class returnType{
        int depth = 0;
        boolean has1 = false;
        boolean has2 = false;
        public returnType(int depth, boolean has1, boolean has2){
            this.depth = depth;
            this.has1 = has1;
            this.has2 = has2;
        }
    }
}

   public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        HashSet<Integer> set = new HashSet<Integer>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        map.put(root.val,-1);
        queue.add(root);
        while(!map.containsKey(o1) || !map.containsKey(o2)) {
            TreeNode poll = queue.poll();
            if(poll.left != null) {
                map.put(poll.left.val,poll.val);
                queue.add(poll.left);
            }
            if(poll.right != null) {
                map.put(poll.right.val,poll.val);
                queue.add(poll.right);
            }
        }
        while(map.containsKey(o1)) {
            set.add(o1);
            o1 = map.get(o1);
        }
        while(!set.contains(o2)) {
            o2 = map.get(o2);
        }
        return  o2;
    }

哪位大神帮我改改啊！！超时了
public ArrayList<TreeNode> getPath(TreeNode root,int num){
        ArrayList<TreeNode> list=new ArrayList();
        while(true){
            while(root!=null){
                list.add(root);
                if(root.val==num){
                   return list;
                }
                root=root.left;
            }
            TreeNode p=list.remove(list.size()-1);
            if(p.right!=null){
                list.add(p);
                root=p.right;
            }
        }
     }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        ArrayList<TreeNode> p1=getPath(root,o1);
         ArrayList<TreeNode> p2=getPath(root,o2);
         int res=-1;
         for(int i=0;i<p1.size()&&i<p2.size();i++){
            int x=p1.get(i).val;
            int y=p2.get(i).val;
            if(x==y){
                res=x;
            }
         }
         return res;
    }

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        //返回父节点.val
        if(root==null) return -1;
        if(root.val==o1) return o1;
        if(root.val==o2) return o2;
        int ans=build(root,o1,o2);
        return ans;
    }
    public int build(TreeNode root,int o1,int o2){
        if(root==null) return -1;
        if(root.val==o1) return o1;
        if(root.val==o2) return o2;
        //后序遍历
        int leftV=build(root.left,o1,o2);
        int rightV=build(root.right,o1,o2);
        if(leftV==-1&&rightV==-1)  return -1;
        if(leftV!=-1&&rightV==-1)  return leftV;
        if(leftV==-1&&rightV!=-1)  return rightV;
        if(leftV!=-1&&rightV!=-1)  return root.val;
        return -1; 
    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        Map<Integer,Integer> parent=new HashMap<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        parent.put(root.val,Integer.MAX_VALUE);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(node.left!=null){
                queue.add(node.left);
                parent.put(node.left.val,node.val);
            }
            if(node.right!=null){
                queue.add(node.right);
                parent.put(node.right.val,node.val);
            }
        }
        ArrayList<Integer> path=new ArrayList<>();
        while(parent.containsKey(o1)){
            path.add(o1);
            o1=parent.get(o1);
        }
        while(!path.contains(o2)){
            o2=parent.get(o2);
        }
        return o2;
    }
}

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        //return getCommonAncestor(root, o1, o2).val;
        return lowestCommonAncestor1(root, o1, o2);
    }
    //采用递归-先序遍历+回溯方式实现
    //如果当前root节点和o1,o2其中一个想等则说明此节点有可能为公共祖先节点，因为节点值是唯一的
    //如果此节点不是祖先节点则说明另外一个节点是在右子树，则需要增加判断 如果left和right值不为null时
    //则说明当前root为公共祖先，否则就是o1,o2其中一个节点
    //从上往下根据前序遍历，再从下往上回溯，则如果left和right不为null时则表明是两个节点的最近公共祖先
    private TreeNode getCommonAncestor(TreeNode root, int o1, int o2) {
        if (root == null || root.val == o1 || root.val == o2) {
            return root;
        }
        TreeNode left = getCommonAncestor(root.left, o1, o2);
        TreeNode right = getCommonAncestor(root.right, o1, o2);

        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;

    }
    //使用堆栈来实现
    //先查找一个值o1，把根节点到o1的路径放入栈中，也就是找到根节点到O1的路径，当找到o1时，o2可以通过此
    //路径上的某个节点肯定能找到，如果通过这个节点找到了o2，就返回这个节点即可(因为这个节点是o1和o2的公共祖先节点，由于栈是后进先出的特性，所以能够找到两个节点的最近公共祖先)

    private int lowestCommonAncestor1(TreeNode root, int o1, int o2) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        if (root == null) {
            return -1;
        }
        search(root, stack, o2);
        while (!stack.isEmpty()) {
            TreeNode e = stack.pop();
            if (find(e, o1)) {
                return e.val;
            }
        }
        return -1;
    }

    private boolean find(TreeNode p, int v) {
        if (p.val == v) {
            return true;
        }
        boolean result1 = false;
        boolean result2 = false;
        if (p.left != null ) {
            result1 = find(p.left, v);
        }
        if (!result1 && p.right != null) {
            result2 = find(p.right, v);
        }
        return result1 || result2;
    }

    private boolean search(TreeNode root, Stack<TreeNode> stack, int o1) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        if (root.val == o1) {
            return true;
        }
        boolean result1 = false;
        boolean result2 = false;
        result1 =  search(root.left, stack, o1);
        if (!result1) {
            result2 =  search(root.right, stack, o1);
        }

        if (!result1 && !result2) {
            stack.pop();
        }
        return result1 || result2;

    }

}

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        TreeNode res = dfs(root, o1, o2);
        return res.val;
    }
    
    TreeNode dfs(TreeNode root, int p, int q) {
        if(root == null) return null;
        if(root.val == p || root.val == q) return root;
        TreeNode  left = dfs(root.left, p, q);
        TreeNode  right = dfs(root.right, p, q);
        if(left != null && right != null) return root;
        return left == null ? right : left;
    }

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    //存父节点和左右值入parent--找对应值的节点并不断往上找父节点入visited
     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 o1, int o2) {
        // write code here
        dfs(root);
        myself(root);
        TreeNode o1_node=self.get(o1);
        TreeNode o2_node=self.get(o2);
        while(o1_node!=null){
            visited.add(o1_node.val);
            o1_node=parent.get(o1_node.val);
        }
        while(o2_node!=null){
            if(visited.contains(o2_node.val)){return o2_node.val;}
            o2_node=parent.get(o2_node.val);
        }
        return root.val;
    }
}

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

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root==null){
            return -1;
        }
        if(root.val==o1||root.val==o2){
            return root.val;
        }
        int left = lowestCommonAncestor(root.left,o1,o2);
        int right = lowestCommonAncestor(root.right,o1,o2);
        if(left!=-1 && right!=-1){
            return root.val;
        }
        return Math.max(left,right);
    }

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        if (root == null) return -1;
        if (root.val == o1 || root.val == o2) {
            return root.val;
        }
        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);
        if (left == -1) return right;
        if (right == -1) return left;
        return root.val;
    }

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root == null){
            return -1;
        }
        // 如果找到两个节点之一，直接返回该节点，没有继续往下遍历的必要
        if(root.val == o1 || root.val == o2){
            return root.val;
        }
        int left = lowestCommonAncestor(root.left,o1,o2);
        int right = lowestCommonAncestor(root.right,o1,o2);
        // 如果两节点在左右子树说明它是最近公共祖先，返回该值
        if(left != -1 && right !=-1){
            return root.val;
        }
        // 左子树已找到最近公共祖先，直接返回左子树
        if(left != -1){
            return left;
        }
        // 右子树已找到最近公共祖先，直接返回右子树
        if(right != -1){
            return right;
        }
        return -1;
    }