LeetCode 1719: Number Of Ways To Reconstruct A Tree Solution

Master LeetCode problem 1719 (Number Of Ways To Reconstruct A Tree), a hard 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.

1719. Number Of Ways To Reconstruct A Tree

Hard

Tree Graph

Problem Explanation

Explanation:

To solve this problem, we can follow these steps:

Build a graph using the pairs where each node represents a unique value in the pairs array.
Determine the root of the tree by finding the node with no incoming edges.
Perform a topological sort to ensure that the tree structure is valid.
Check if the tree can be uniquely reconstructed based on the given pairs.

If the tree can be uniquely reconstructed, there will be only one valid rooted tree. If there are multiple valid rooted trees possible, then there will be more than one way to reconstruct the tree. If there is no valid rooted tree possible, then return 0.

Time complexity: O(NlogN) where N is the number of pairs Space complexity: O(N)

: :

Solution Code

class Solution {
    public int checkWays(int[][] pairs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();

        for (int[] pair : pairs) {
            graph.computeIfAbsent(pair[0], k -> new HashSet<>()).add(pair[1]);
            graph.computeIfAbsent(pair[1], k -> new HashSet<>()).add(pair[0]);
            indegree.put(pair[0], indegree.getOrDefault(pair[0], 0) + 1);
            indegree.put(pair[1], indegree.getOrDefault(pair[1], 0) + 1);
        }

        int root = -1;
        for (int node : indegree.keySet()) {
            if (indegree.get(node) == pairs.length - 1) {
                if (root == -1) {
                    root = node;
                } else {
                    return 2;
                }
            }
        }

        if (root == -1) return 0;

        int[] children = new int[2];
        for (int child : graph.get(root)) {
            children[indegree.get(child) > 1 ? 1 : 0] = child;
        }

        return isUnique(root, children, graph) ? 1 : 2;
    }

    private boolean isUnique(int root, int[] children, Map<Integer, Set<Integer>> graph) {
        for (int child : children) {
            Set<Integer> set = new HashSet<>(graph.get(child));
            set.retainAll(graph.get(root));
            if (set.size() > 1 || (set.size() == 1 && !isUnique(child, new int[]{set.iterator().next(), root}, graph))) {
                return false;
            }
        }
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1719 (Number Of Ways To Reconstruct A Tree)?

This page provides optimized solutions for LeetCode problem 1719 (Number Of Ways To Reconstruct A Tree) 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 1719 (Number Of Ways To Reconstruct A Tree)?

The time complexity for LeetCode 1719 (Number Of Ways To Reconstruct A Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1719 on DevExCode?

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

Back to LeetCode Solutions