/* 返回第一次包含2个的目标节点，如果不包含则为null

1. dfs 顺序：包括自身的子树存在几个目标节点
2. dfs 状态：节点

*/

/* 直接判断， 题目条件必须保证合法
1. lca 的位置有三种可能： root，在left 中， 在 right 中
2.1 lca 为 root时， left 里面只有一个目标节点，非空
2.2 lca 在 left 中时， 递归处理left ，此时right 必定不存在lca
2.3 lca 在right 中时， 同理left
*/


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return lca2(root, p, q);
    }

    public TreeNode lca2(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        var left = lca2(root.left ,p, q);
        var right = lca2(root.right, p, q);

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

    public TreeNode lca1(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> list = new ArrayList<>();
        dfs(root, p, q, list);
        return list.size() == 1 ? list.get(0): null;
    }

    public int dfs(TreeNode root, TreeNode p, TreeNode q, List<TreeNode> r) {
        if (root == null) return 0;
        int res =  (root.val == p.val || root.val == q.val?  1 : 0) + dfs (root.left, p, q, r) + dfs(root.right, p, q, r);
        if (res == 2 && r.isEmpty()) r.add(root);
        return res;
    }


}