LeetCode 1676: Lowest Common Ancestor of a Binary Tree IV Solution

Master LeetCode problem 1676 (Lowest Common Ancestor of a Binary Tree IV), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1676. Lowest Common Ancestor of a Binary Tree IV

Medium

Hash Table Tree Depth-First Search Binary Tree

Problem Explanation

Explanation:

To find the lowest common ancestor (LCA) of two nodes in a binary tree, we can perform a recursive depth-first search (DFS) starting from the root. At each step, we check if the current node is one of the given nodes or if one of the nodes is found in the left or right subtree. If both nodes are found in different subtrees of the current node, then the current node is the LCA.

To solve this problem, we can extend this approach to handle multiple nodes. We can maintain a set of target nodes and a count of found nodes in the subtree rooted at the current node. We perform a post-order DFS traversal, updating the count of found nodes from the left and right subtrees. If the count of found nodes equals the number of target nodes, then the current node is the LCA.

Algorithm:

Initialize a set to store the target nodes.
Perform a post-order DFS traversal starting from the root:
- Recursively visit the left child and right child.
- Update the count of found nodes from the left and right subtrees.
- If the current node is in the set of target nodes, increment the count of found nodes.
- If the count of found nodes equals the number of target nodes, set the LCA to the current node.
Return the LCA.

Time Complexity:

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. We visit each node once during the post-order DFS traversal.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This space is used for the recursive call stack during the DFS traversal.

: :

Solution Code

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        Set<TreeNode> targets = new HashSet<>(Arrays.asList(nodes));
        return dfs(root, targets);
    }
    
    private TreeNode dfs(TreeNode node, Set<TreeNode> targets) {
        if (node == null) return null;
        
        TreeNode left = dfs(node.left, targets);
        TreeNode right = dfs(node.right, targets);
        
        if (targets.contains(node)) {
            return node;
        }
        
        int count = 0;
        if (left != null) count++;
        if (right != null) count++;
        if (count == targets.size()) {
            return node;
        }
        
        return left != null ? left : right;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1676 (Lowest Common Ancestor of a Binary Tree IV)?

This page provides optimized solutions for LeetCode problem 1676 (Lowest Common Ancestor of a Binary Tree IV) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1676 (Lowest Common Ancestor of a Binary Tree IV)?

The time complexity for LeetCode 1676 (Lowest Common Ancestor of a Binary Tree IV) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1676 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1676 in Java, C++, or Python.

Back to LeetCode Solutions