1676. Lowest Common Ancestor of a Binary Tree IV

一刷 05/2022

Version #1 Recursion 

Time O(N)

Space O(N)

Runtime: 11 ms, faster than 21.65% of Java online submissions for Lowest Common Ancestor of a Binary Tree IV.

Memory Usage: 55.6 MB, less than 12.81% of Java online submissions for Lowest Common Ancestor of a Binary Tree IV.

/**

 * 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[] nodes) {

        if (root == null || nodes == null) {

            return null;

        }

        Set<Integer> set = new HashSet<>();

        for (TreeNode node : nodes) {

            set.add(node.val);

        }

        TreeNode[] result = new TreeNode[1];

        countTarget(root, set, result);

        return result[0];

    }

    

    private int countTarget(TreeNode node, Set<Integer> set, TreeNode[] result) {

        if (node == null) {

            return 0;

        }

        int targetSize = set.size();

        int left = countTarget(node.left, set, result);

        if (left == targetSize) {

            return left;

        }

        int right = countTarget(node.right, set, result);

        if (right == targetSize) {

            return right;

        }

        int count = left + right;

        if (set.contains(node.val)) {

            count++;

        }

        if (count == targetSize) {

            result[0] = node;

        }

        return count;

    }

}