【牛客】BM38在二叉树中找到两个节点的最近公共祖先

在二叉树中找到两个节点的最近公共祖先-牛客网"https://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116?tpId=295&tqId=1024325&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj"

描述

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足 1≤n≤105 , 节点值val满足区间 [0,n)

要求：时间复杂度 O*(*n)

注：本题保证二叉树中每个节点的val值均不相同。

如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：

所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。

节点本身可以视为自己的祖先

示例1

输入：
{3,5,1,6,2,0,8,#,#,7,4},5,1
返回值：
3    

示例2

输入：
{3,5,1,6,2,0,8,#,#,7,4},2,7
返回值：
2

题解

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // list记录搜索路径
        ArrayList<Integer> list1 = new ArrayList<>();
        ArrayList<Integer> list2 = new ArrayList<>();
        find(root, o1, list1);
        find(root, o2, list2);
        
        int ps = root.val;
        int n = Math.min(list1.size(), list2.size());
        for(int i=0; i<n; i++){
            //System.out.println(i+" | "+list1.get(i)+" | "+list2.get(i));
            //这里的 equals 不能用 ==
            if(list1.get(i).equals(list2.get(i))){
                ps = list1.get(i);
            }else{
                break;
            }
        }
        return ps;
    }

    public boolean find(TreeNode node, int o, ArrayList<Integer> list){
        list.add(node.val);
        if(node.val == o){
            return true;
        }
        if(node.left != null && find(node.left, o, list)){
            return true;
        }
        if(node.right != null && find(node.right, o, list)){
            return true;
        }

        list.remove(list.size()-1);
        return false;
    }