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

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;
    }