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

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整型
     */
    boolean flag = false;
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();
        findPath(root,o1,list1);
        flag = false;
        findPath(root,o2,list2);
        int i = 0;
        int val = 0;
        while(i<Math.min(list1.size(),list2.size())){
            int path1 = list1.get(i);
            int path2 = list2.get(i);
            i++;
            if(path1 == path2){
                val = path1;
            }else{
                break;
            }
        }
        return val;
    }
    //回溯
    public void findPath(TreeNode root, int o,List<Integer> path){
        if(root == null){
            return;
        }
        path.add(root.val);
        int size = path.size();
        if(root.val == o){
            flag = true;
            return;
        }
        findPath(root.left,o,path);
        if(flag){
            return;
        }
        findPath(root.right,o,path);
        if(flag){
            return;
        }
        path.remove(size - 1);
    }
}