Easy Solution || Explained Well || java
Objective\nFor each node, we want to calculate a score. This score is the product of the sizes of the subtrees of its children and the remaining nodes outside t
Objective\nFor each node, we want to calculate a score. This score is the product of the sizes of the subtrees of its children and the remaining nodes outside these subtrees. We need to find out how many nodes have the highest score.\n\nSteps to Solve the Problem\nCreate the Binary Tree:\n\nConvert the parents array into a tree structure so we can easily navigate and calculate subtree sizes.\nTraverse the Tree:\n\nVisit each node and calculate the size of its subtrees.\nCalculate the score for each node using the sizes of its subtrees and the remaining nodes.\nTrack Scores:\n\nKeep track of all scores and identify the maximum score.\nCount how many nodes have this maximum score.\nDetailed Steps\nStep 1: Create the Binary Tree\nWe need to create nodes and link them based on the parents array.\n\nEach node is represented by a TreeNode class.\nWe store all nodes in an array and then link them according to their parent indices.\nHere\'s a method to create the tree:\n\n```\n\nclass TreeNode {\n    int val;\n    TreeNode left;\n    TreeNode right;\n\n    TreeNode(int val) {\n        this.val = val;\n        this.left = null;\n        this.right = null;\n    }\n}\n\npublic TreeNode createTree(int[] parents) {\n    int n = parents.length;\n    TreeNode[] nodes = new TreeNode[n];\n    \n    // Create all nodes\n    for (int i = 0; i < n; i++) {\n        nodes[i] = new TreeNode(i);\n    }\n\n    TreeNode root = null;\n    \n    // Link nodes according to the parents array\n    for (int i = 0; i < n; i++) {\n        if (parents[i] == -1) {\n            root = nodes[i];  // The root node\n        } else {\n            TreeNode parent = nodes[parents[i]];\n            if (parent.left == null) {\n                parent.left = nodes[i];\n            } else {\n                parent.right = nodes[i];\n            }\n        }\n    }\n    \n    return root;\n}\n```\nStep 2: Traverse the Tree and Calculate Scores\nWe will use a post-order traversal (process left subtree, right subtree, then the node) to calculate the size of each subtree and the score for each node.\n\n```\n\nclass Solution {\n    \n    HashMap<Long, List<Long>> scoreMap = new HashMap<>();\n    int totalNodes = 0;\n    long maxScore = 0;\n\n    public int countHighestScoreNodes(int[] parents) {\n        TreeNode root = createTree(parents);\n        totalNodes = parents.length;\n        calculateScores(root);\n        return scoreMap.get(maxScore).size();\n    }\n\n    public int calculateScores(TreeNode node) {\n        if (node == null) return 0;\n        \n        int leftSize = calculateScores(node.left);\n        int rightSize = calculateScores(node.right);\n        \n        long score = 1;\n        if (leftSize != 0) score *= leftSize;\n        if (rightSize != 0) score *= rightSize;\n        if (totalNodes - leftSize - rightSize - 1 != 0) score *= (totalNodes - leftSize - rightSize - 1);\n\n        maxScore = Math.max(score, maxScore);\n        scoreMap.putIfAbsent(score, new ArrayList<>());\n        scoreMap.get(score).add((long)node.val);\n\n        return leftSize + rightSize + 1;\n    }\n\n    public TreeNode createTree(int[] parents) {\n        int n = parents.length;\n        TreeNode[] nodes = new TreeNode[n];\n        \n        for (int i = 0; i < n; i++) {\n            nodes[i] = new TreeNode(i);\n        }\n\n        TreeNode root = null;\n        \n        for (int i = 0; i < n; i++) {\n            if (parents[i] == -1) {\n                root = nodes[i];  // The root node\n            } else {\n                TreeNode parent = nodes[parents[i]];\n                if (parent.left == null) {\n                    parent.left = nodes[i];\n                } else {\n                    parent.right = nodes[i];\n                }\n            }\n        }\n        \n        return root;\n    }\n}\n```\nExplanation of the Code\nTreeNode Class:\n\nRepresents each node with val, left, and right.\ncreateTree Method:\n\nConverts the parents array into a tree structure.\ncalculateScores Method:\n\nRecursively calculates the size of each subtree.\nComputes the score for each node and updates the maxScore.\nUses a HashMap scoreMap to keep track of scores and corresponding nodes.\ncountHighestScoreNodes Method:\n\nUses the above methods to create the tree, calculate scores, and return the count of nodes with the highest score.\nSummary\nThis solution involves creating the tree from the parents array, traversing it to calculate the scores for each node, and then determining how many nodes have the highest score. The use of a HashMap helps in efficiently counting nodes with the same score, and the traversal ensures all nodes are processed correctly.
['Tree']