1644. Lowest Common Ancestor of a Binary Tree II

這題

If either node p or q does not exist in the tree, return null

所以用 236 第二種解法可以 work (算 count)

T: O(n)

S: O(h) ~O(n)

class Solution {
    TreeNode res = null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return res;
    }
    private int dfs(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left, p, q);
        int right = dfs(node.right, p, q);
        int self = (node.val == p.val || node.val == q.val) ? 1 : 0;
        int count = left + right + self;
        if (count == 2 && res == null) {
            res = node;
        }
        return count;
    }
}

/*
If either node p or q does not exist in the tree, return null
*/