1644. Lowest Common Ancestor of a Binary Tree II

一刷 05/2022

Version #1 Recursion 

Runtime: 14 ms, faster than 56.79% of Java online submissions for Lowest Common Ancestor of a Binary Tree II.

Memory Usage: 72.7 MB, less than 15.25% of Java online submissions for Lowest Common Ancestor of a Binary Tree II.

/**

 * 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) {

        TreeNode[] result = new TreeNode[1];

        countTarget(root, p, q, result);

        return result[0];

        

    }

    private int countTarget(TreeNode node, TreeNode p, TreeNode q, TreeNode[] result) {

        if (node == null) {

            return 0;

        }

        int left = countTarget(node.left, p, q, result);

        if (left == 2) {

            return left;

        }

        int right = countTarget(node.right, p, q, result);

        if (right == 2) {

            return right;

        }

        int count = left + right;

        if (node == p || node == q) {

            count++;

        }

        if (count == 2) {

            result[0] = node;

        }

        return count;

    }

}