SkylineWebZ

Problem Statement: Word Break II Given a string s and a list of words wordDict, return all possible sentence(s) where each sentence is a valid segmentation of s into words from wordDict. The solution should return a list of all possible sentences. Note: Example Example 1: Input:”catsanddog”wordDict = [“cat”, “cats”, “and”, “sand”, “dog”] Output:[“cats and dog”, “cat sand dog”] Example 2: Input:”pineapplepenapple”wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”] Output:[“pine apple pen apple”, “pineapple pen apple”, “pine applepen apple”] Example 3: Input:”catsandog”wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] Output:[] Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdlib.h>#include <stdbool.h>#define MAX 1000void findWordBreaks(char* s, int start, char** wordDict, int wordDictSize, bool* dp, char*** result, int* returnSize) { if (start == strlen(s)) { result[*returnSize] = malloc(sizeof(char*) * 2); result[*returnSize][0] = strdup(“”); (*returnSize)++; return; } if (!dp[start]) return; // Skip if this position cannot be reached for (int i = 0; i < wordDictSize; i++) { int len = strlen(wordDict[i]); if (start + len <= strlen(s) && strncmp(s + start, wordDict[i], len) == 0) { char** tempResult; int tempSize = 0; findWordBreaks(s, start + len, wordDict, wordDictSize, dp, &tempResult, &tempSize); for (int j = 0; j < tempSize; j++) { int newSize = tempSize + 1; result[*returnSize] = realloc(result[*returnSize], sizeof(char*) * newSize); char* newSentence = malloc(strlen(wordDict[i]) + strlen(tempResult[j]) + 2); sprintf(newSentence, “%s %s”, wordDict[i], tempResult[j]); result[*returnSize][newSize – 1] = newSentence; } } }}int main() { char* s = “catsanddog”; char* wordDict[] = {“cat”, “cats”, “and”, “sand”, “dog”}; int wordDictSize = 5; bool dp[MAX]; memset(dp, 0, sizeof(dp)); char*** result = malloc(sizeof(char**) * MAX); int returnSize = 0; findWordBreaks(s, 0, wordDict, wordDictSize, dp, result, &returnSize); for (int i = 0; i < returnSize; i++) { printf(“%s\n”, result[i][0]); } return 0;} C++ #include <iostream>#include <vector>#include <unordered_set>#include <string>#include <algorithm>using namespace std;void dfs(string s, unordered_set<string>& wordSet, vector<string>& currentSentence, vector<string>& result, vector<bool>& dp) { if (s.empty()) { string sentence = “”; for (int i = 0; i < currentSentence.size(); i++) { sentence += currentSentence[i]; if (i != currentSentence.size() – 1) sentence += ” “; } result.push_back(sentence); return; } if (!dp[s.size()]) return; for (int i = 1; i <= s.size(); i++) { string word = s.substr(0, i); if (wordSet.find(word) != wordSet.end()) { currentSentence.push_back(word); dfs(s.substr(i), wordSet, currentSentence, result, dp); currentSentence.pop_back(); } }}vector<string> wordBreak(string s, unordered_set<string>& wordSet) { int n = s.length(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.find(s.substr(j, i – j)) != wordSet.end()) { dp[i] = true; break; } } } vector<string> result; vector<string> currentSentence; if (dp[n]) dfs(s, wordSet, currentSentence, result, dp); sort(result.begin(), result.end()); return result;}int main() { unordered_set<string> wordSet = {“cat”, “cats”, “and”, “sand”, “dog”}; string s = “catsanddog”; vector<string> result = wordBreak(s, wordSet); for (const auto& sentence : result) { cout << sentence << endl; } return 0;} Java import java.util.*;public class WordBreakII { public static void dfs(String s, Set<String> wordSet, List<String> currentSentence, List<String> result, boolean[] dp) { if (s.isEmpty()) { result.add(String.join(” “, currentSentence)); return; } if (!dp[s.length()]) return; for (int i = 1; i <= s.length(); i++) { String word = s.substring(0, i); if (wordSet.contains(word)) { currentSentence.add(word); dfs(s.substring(i), wordSet, currentSentence, result, dp); currentSentence.remove(currentSentence.size() – 1); } } } public static List<String> wordBreak(String s, Set<String> wordSet) { int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } List<String> result = new ArrayList<>(); if (dp[n]) { List<String> currentSentence = new ArrayList<>(); dfs(s, wordSet, currentSentence, result, dp); } Collections.sort(result); return result; } public static void main(String[] args) { Set<String> wordSet = new HashSet<>(Arrays.asList(“cat”, “cats”, “and”, “sand”, “dog”)); String s = “catsanddog”; List<String> result = wordBreak(s, wordSet); for (String sentence : result) { System.out.println(sentence); } }} Python pythonCopy codedef dfs(s, wordSet, currentSentence, result, dp): if not s: result.append(” “.join(currentSentence)) return if not dp[len(s)]: return for i in range(1, len(s) + 1): word = s[:i] if word in wordSet: currentSentence.append(word) dfs(s[i:], wordSet, currentSentence, result, dp) currentSentence.pop() def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break result = [] if dp[n]: currentSentence = [] dfs(s, wordSet, currentSentence, result, dp) result.sort() return result # Example s = “catsanddog” wordDict = [“cat”, “cats”, “and”, “sand”, “dog”] print(wordBreak(s, wordDict)) # Output: [“cats and dog”, “cat sand dog”] C# using System;using System.Collections.Generic;public class WordBreakII { public static void Dfs(string s, HashSet<string> wordSet, List<string> currentSentence, List<string> result, bool[] dp) { if (s.Length == 0) { result.Add(string.Join(” “, currentSentence)); return; } if (!dp[s.Length]) return; for (int i = 1; i <= s.Length; i++) { string word = s.Substring(0, i); if (wordSet.Contains(word)) { currentSentence.Add(word); Dfs(s.Substring(i), wordSet, currentSentence, result, dp); currentSentence.RemoveAt(currentSentence.Count – 1); } } } public static List<string> WordBreak(string s, HashSet<string> wordSet) { int n = s.Length; bool[] dp = new bool[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.Contains(s.Substring(j, i – j))) { dp[i] = true; break; } } } List<string> result = new List<string>(); if (dp[n]) { List<string> currentSentence = new List<string>(); Dfs(s, wordSet, currentSentence, result, dp); } result.Sort(); return result; } public static void Main() { HashSet<string> wordSet = new HashSet<string> { “cat”, “cats”, “and”, “sand”, “dog” }; string s = “catsanddog”; List<string> result = WordBreak(s, wordSet); foreach (var sentence in result) { Console.WriteLine(sentence); } }} JavaScript function dfs(s, wordSet, currentSentence, result, dp) { if (s === “”) { result.push(currentSentence.join(” “)); return; } if (!dp[s.length]) return; for (let i = 1; i <= s.length; i++) { const word = s.slice(0, i); if (wordSet.has(word)) { currentSentence.push(word); dfs(s.slice(i), wordSet, currentSentence, result, dp); currentSentence.pop(); } }}function wordBreak(s, wordDict) { const wordSet = new Set(wordDict);

Problem Statement: Word Break Given a string s and a dictionary of words wordDict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: Example Example 1: Input: s = “leetcode”, wordDict = [“leet”, “code”]Output: trueExplanation: Return true because “leetcode” can be segmented as “leet code”. Example 2: Input: s = “applepenapple”, wordDict = [“apple”, “pen”]Output: trueExplanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Example 3: Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]Output: falseExplanation: Return false because “catsandog” cannot be segmented into words from the dictionary. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>bool wordBreak(char* s, char** wordDict, int wordDictSize) { int n = strlen(s); bool dp[n + 1]; memset(dp, 0, sizeof(dp)); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < wordDictSize; j++) { int len = strlen(wordDict[j]); if (i >= len && dp[i – len] && strncmp(s + i – len, wordDict[j], len) == 0) { dp[i] = true; break; } } } return dp[n];}int main() { char* wordDict[] = {“leet”, “code”}; int wordDictSize = sizeof(wordDict) / sizeof(wordDict[0]); char s[] = “leetcode”; printf(“%d\n”, wordBreak(s, wordDict, wordDictSize)); // Output: 1 (true) return 0;} C++ #include <iostream>#include <vector>#include <unordered_set>#include <string>using namespace std;bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> wordSet(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n + 1, false); dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.find(s.substr(j, i – j)) != wordSet.end()) { dp[i] = true; break; } } } return dp[n];}int main() { vector<string> wordDict = {“leet”, “code”}; string s = “leetcode”; cout << wordBreak(s, wordDict) << endl; // Output: 1 (true) return 0;} Java import java.util.*;public class WordBreak { public static boolean wordBreak(String s, List<String> wordDict) { Set<String> wordSet = new HashSet<>(wordDict); int n = s.length(); boolean[] dp = new boolean[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; } public static void main(String[] args) { List<String> wordDict = Arrays.asList(“leet”, “code”); String s = “leetcode”; System.out.println(wordBreak(s, wordDict)); // Output: true }} Python def wordBreak(s: str, wordDict: list) -> bool: wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True for i in range(1, n + 1): for j in range(i): if dp[j] and s[j:i] in wordSet: dp[i] = True break return dp[n]# Examples = “leetcode”wordDict = [“leet”, “code”]print(wordBreak(s, wordDict)) # Output: True C# using System;using System.Collections.Generic;public class WordBreak { public static bool WordBreak(string s, IList<string> wordDict) { HashSet<string> wordSet = new HashSet<string>(wordDict); int n = s.Length; bool[] dp = new bool[n + 1]; dp[0] = true; for (int i = 1; i <= n; i++) { for (int j = 0; j < i; j++) { if (dp[j] && wordSet.Contains(s.Substring(j, i – j))) { dp[i] = true; break; } } } return dp[n]; } public static void Main() { List<string> wordDict = new List<string> { “leet”, “code” }; string s = “leetcode”; Console.WriteLine(WordBreak(s, wordDict)); // Output: True }} JavaScript function wordBreak(s, wordDict) { const wordSet = new Set(wordDict); const n = s.length; const dp = new Array(n + 1).fill(false); dp[0] = true; for (let i = 1; i <= n; i++) { for (let j = 0; j < i; j++) { if (dp[j] && wordSet.has(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n];}console.log(wordBreak(“leetcode”, [“leet”, “code”])); // Output: true Summary

Problem Statement: Palindrome Partitioning II Given a string s, you need to partition it such that every substring of the partition is a palindrome. Return the minimum number of cuts required to partition s such that every substring is a palindrome. Example Example 1: Input: s = “aab” Output: 1Explanation: The palindrome partitioning [“aa”, “b”] could be made with 1 cut. Example 2: Input: s = “a” Output: 0Explanation: The string is already a palindrome, so no cuts are needed. Example 3: Input: s = “abac” Output: 1Explanation: The palindrome partitioning [“aba”, “c”] could be made with 1 cut. Approach and Algorithm Code in Multiple Languages C #include <stdio.h>#include <string.h>#include <stdbool.h>#define MAX 1000int minCut(char* s) { int n = strlen(s); bool palindrome[n][n]; int dp[n+1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; memset(palindrome, 0, sizeof(palindrome)); for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = (dp[i] < dp[j] + 1) ? dp[i] : dp[j] + 1; } } } return dp[n – 1];}int main() { char s[] = “aab”; printf(“%d\n”, minCut(s)); return 0;} C++ #include <iostream>#include <vector>#include <cstring>using namespace std;int minCut(string s) { int n = s.length(); vector<vector<bool>> palindrome(n, vector<bool>(n, false)); vector<int> dp(n + 1, n); dp[0] = -1; // no cut needed for empty string for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = min(dp[i], dp[j] + 1); } } } return dp[n – 1];}int main() { string s = “aab”; cout << minCut(s) << endl; return 0;} Java public class PalindromePartitioning { public static int minCut(String s) { int n = s.length(); boolean[][] palindrome = new boolean[n][n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i][j] = (s.charAt(i) == s.charAt(j)) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void main(String[] args) { String s = “aab”; System.out.println(minCut(s)); }} Python def minCut(s: str) -> int: n = len(s) palindrome = [[False] * n for _ in range(n)] dp = [i for i in range(-1, n)] for i in range(n – 1, -1, -1): for j in range(i, n): palindrome[i][j] = (s[i] == s[j]) and (j – i <= 2 or palindrome[i + 1][j – 1]) for i in range(n): if palindrome[0][i]: dp[i] = 0 else: for j in range(i): if palindrome[j + 1][i]: dp[i] = min(dp[i], dp[j] + 1) return dp[n – 1]# Examples = “aab”print(minCut(s)) # Output: 1 C# using System;public class PalindromePartitioning { public static int MinCut(string s) { int n = s.Length; bool[,] palindrome = new bool[n, n]; int[] dp = new int[n + 1]; for (int i = 0; i <= n; i++) dp[i] = i – 1; for (int i = n – 1; i >= 0; i–) { for (int j = i; j < n; j++) { palindrome[i, j] = (s[i] == s[j]) && (j – i <= 2 || palindrome[i + 1, j – 1]); } } for (int i = 0; i < n; i++) { if (palindrome[0, i]) dp[i] = 0; else { for (int j = 0; j < i; j++) { if (palindrome[j + 1, i]) dp[i] = Math.Min(dp[i], dp[j] + 1); } } } return dp[n – 1]; } public static void Main() { string s = “aab”; Console.WriteLine(MinCut(s)); // Output: 1 }} JavaScript function minCut(s) { const n = s.length; const palindrome = Array.from(Array(n), () => Array(n).fill(false)); const dp = Array.from({ length: n + 1 }, (_, i) => i – 1); for (let i = n – 1; i >= 0; i–) { for (let j = i; j < n; j++) { palindrome[i][j] = (s[i] === s[j]) && (j – i <= 2 || palindrome[i + 1][j – 1]); } } for (let i = 0; i < n; i++) { if (palindrome[0][i]) dp[i] = 0; else { for (let j = 0; j < i; j++) { if (palindrome[j + 1][i]) dp[i] = Math.min(dp[i], dp[j] + 1); } } } return dp[n – 1];}console.log(minCut(“aab”)); // Output: 1 Summary

Problem Statement: Palindrome Partitioning Given a string s, partition the string such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Definition: Example: Example 1: Input: plaintextCopy code”aab” Output: plaintextCopy code[[“a”, “a”, “b”], [“aa”, “b”]] Explanation: The string “aab” can be split in two ways where each substring is a palindrome: Example 2: Input: plaintextCopy code”efe” Output: plaintextCopy code[[“e”, “f”, “e”], [“efe”]] Explanation: The string “efe” can be split into: Approach: We can solve this problem using backtracking and dynamic programming. Backtracking Approach: Algorithm: Code Implementation: 1. C++: #include <iostream>#include <vector>#include <string>using namespace std;class Solution {public: bool isPalindrome(const string& s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } void backtrack(const string& s, int start, vector<string>& current, vector<vector<string>>& result) { if (start == s.length()) { result.push_back(current); return; } for (int end = start; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.push_back(s.substr(start, end – start + 1)); backtrack(s, end + 1, current, result); current.pop_back(); // backtrack } } } vector<vector<string>> partition(string s) { vector<vector<string>> result; vector<string> current; backtrack(s, 0, current, result); return result; }};int main() { Solution sol; string s = “aab”; vector<vector<string>> result = sol.partition(s); for (const auto& partition : result) { for (const auto& str : partition) { cout << str << ” “; } cout << endl; } return 0;} 2. Java: import java.util.ArrayList;import java.util.List;public class Solution { public boolean isPalindrome(String s, int start, int end) { while (start < end) { if (s.charAt(start) != s.charAt(end)) return false; start++; end–; } return true; } public void backtrack(String s, int start, List<String> current, List<List<String>> result) { if (start == s.length()) { result.add(new ArrayList<>(current)); return; } for (int end = start; end < s.length(); ++end) { if (isPalindrome(s, start, end)) { current.add(s.substring(start, end + 1)); backtrack(s, end + 1, current, result); current.remove(current.size() – 1); // backtrack } } } public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); List<String> current = new ArrayList<>(); backtrack(s, 0, current, result); return result; } public static void main(String[] args) { Solution sol = new Solution(); String s = “aab”; List<List<String>> result = sol.partition(s); for (List<String> partition : result) { for (String str : partition) { System.out.print(str + ” “); } System.out.println(); } }} 3. Python: class Solution: def isPalindrome(self, s, start, end): while start < end: if s[start] != s[end]: return False start += 1 end -= 1 return True def backtrack(self, s, start, current, result): if start == len(s): result.append(list(current)) return for end in range(start, len(s)): if self.isPalindrome(s, start, end): current.append(s[start:end+1]) self.backtrack(s, end+1, current, result) current.pop() # backtrack def partition(self, s): result = [] self.backtrack(s, 0, [], result) return result# Example usagesol = Solution()s = “aab”result = sol.partition(s)for partition in result: print(partition) 4. C#: using System;using System.Collections.Generic;public class Solution { public bool IsPalindrome(string s, int start, int end) { while (start < end) { if (s[start] != s[end]) return false; start++; end–; } return true; } public void Backtrack(string s, int start, List<string> current, List<List<string>> result) { if (start == s.Length) { result.Add(new List<string>(current)); return; } for (int end = start; end < s.Length; ++end) { if (IsPalindrome(s, start, end)) { current.Add(s.Substring(start, end – start + 1)); Backtrack(s, end + 1, current, result); current.RemoveAt(current.Count – 1); // backtrack } } } public List<List<string>> Partition(string s) { List<List<string>> result = new List<List<string>>(); List<string> current = new List<string>(); Backtrack(s, 0, current, result); return result; } public static void Main() { Solution sol = new Solution(); string s = “aab”; List<List<string>> result = sol.Partition(s); foreach (var partition in result) { Console.WriteLine(string.Join(” “, partition)); } }} 5. JavaScript: class Solution { isPalindrome(s, start, end) { while (start < end) { if (s[start] !== s[end]) return false; start++; end–; } return true; } backtrack(s, start, current, result) { if (start === s.length) { result.push([…current]); return; } for (let end = start; end < s.length; ++end) { if (this.isPalindrome(s, start, end)) { current.push(s.substring(start, end + 1)); this.backtrack(s, end + 1, current, result); current.pop(); // backtrack } } } partition(s) { let result = []; this.backtrack(s, 0, [], result); return result; }}// Example usage:let sol = new Solution();let s = “aab”;let result = sol.partition(s);result.forEach(partition => { console.log(partition.join(” “));}); Time and Space Complexity:

Problem Statement: Binary Tree Maximum Path Sum Given a binary tree, the task is to find the maximum path sum. The path may start and end at any node in the tree, and you are allowed to move from a node to its left or right child but not upwards to its parent. Path Definition: A path is a sequence of nodes in the tree where each pair of adjacent nodes in the sequence has an edge connecting them. The sum of the path is the sum of the node values along the path. Example: Example 1: Input: -10 / \ 9 20 / \ 15 7 Output: 42 Explanation: The path with the maximum sum is 15 -> 20 -> 7, which sums to 15 + 20 + 7 = 42. Example 2: Input: 1 / \ 2 3 Output: 6 Explanation: The path with the maximum sum is 2 -> 1 -> 3, which sums to 2 + 1 + 3 = 6. Approach: Algorithm: Code Implementation: 1. C: #include <stdio.h>#include <limits.h>struct TreeNode { int val; struct TreeNode* left; struct TreeNode* right;};int maxPathSumHelper(struct TreeNode* root, int* globalMax) { if (root == NULL) { return 0; } int left = maxPathSumHelper(root->left, globalMax); int right = maxPathSumHelper(root->right, globalMax); int maxSingle = (left > right) ? left : right; maxSingle = (maxSingle > 0) ? maxSingle + root->val : root->val; int maxTop = left + right + root->val; *globalMax = (*globalMax > maxTop) ? *globalMax : maxTop; return maxSingle;}int maxPathSum(struct TreeNode* root) { int globalMax = INT_MIN; maxPathSumHelper(root, &globalMax); return globalMax;}int main() { struct TreeNode n1 = { -10, NULL, NULL }; struct TreeNode n2 = { 9, NULL, NULL }; struct TreeNode n3 = { 20, NULL, NULL }; struct TreeNode n4 = { 15, NULL, NULL }; struct TreeNode n5 = { 7, NULL, NULL }; n1.left = &n2; n1.right = &n3; n3.left = &n4; n3.right = &n5; printf(“Maximum Path Sum: %d\n”, maxPathSum(&n1)); return 0;} 2. C++: #include <iostream>#include <climits>using namespace std;struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution {public: int maxPathSumHelper(TreeNode* root, int& globalMax) { if (!root) return 0; int left = max(0, maxPathSumHelper(root->left, globalMax)); int right = max(0, maxPathSumHelper(root->right, globalMax)); int localMax = left + right + root->val; globalMax = max(globalMax, localMax); return max(left, right) + root->val; } int maxPathSum(TreeNode* root) { int globalMax = INT_MIN; maxPathSumHelper(root, globalMax); return globalMax; }};int main() { TreeNode n1(-10), n2(9), n3(20), n4(15), n5(7); n1.left = &n2; n1.right = &n3; n3.left = &n4; n3.right = &n5; Solution sol; cout << “Maximum Path Sum: ” << sol.maxPathSum(&n1) << endl; return 0;} 3. Java: class Solution { int maxPathSumHelper(TreeNode root, int[] globalMax) { if (root == null) return 0; int left = Math.max(0, maxPathSumHelper(root.left, globalMax)); int right = Math.max(0, maxPathSumHelper(root.right, globalMax)); int localMax = left + right + root.val; globalMax[0] = Math.max(globalMax[0], localMax); return Math.max(left, right) + root.val; } public int maxPathSum(TreeNode root) { int[] globalMax = { Integer.MIN_VALUE }; maxPathSumHelper(root, globalMax); return globalMax[0]; }}class TreeNode { int val; TreeNode left, right; TreeNode(int x) { val = x; }}public class Main { public static void main(String[] args) { TreeNode n1 = new TreeNode(-10); TreeNode n2 = new TreeNode(9); TreeNode n3 = new TreeNode(20); TreeNode n4 = new TreeNode(15); TreeNode n5 = new TreeNode(7); n1.left = n2; n1.right = n3; n3.left = n4; n3.right = n5; Solution sol = new Solution(); System.out.println(“Maximum Path Sum: ” + sol.maxPathSum(n1)); }} 4. Python: class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = Noneclass Solution: def maxPathSumHelper(self, root, globalMax): if not root: return 0 left = max(0, self.maxPathSumHelper(root.left, globalMax)) right = max(0, self.maxPathSumHelper(root.right, globalMax)) localMax = left + right + root.val globalMax[0] = max(globalMax[0], localMax) return max(left, right) + root.val def maxPathSum(self, root: TreeNode) -> int: globalMax = [float(‘-inf’)] self.maxPathSumHelper(root, globalMax) return globalMax[0]# Example usageif __name__ == “__main__”: n1 = TreeNode(-10) n2 = TreeNode(9) n3 = TreeNode(20) n4 = TreeNode(15) n5 = TreeNode(7) n1.left = n2 n1.right = n3 n3.left = n4 n3.right = n5 sol = Solution() print(“Maximum Path Sum:”, sol.maxPathSum(n1)) 5. C#: public class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int x) { val = x; }}public class Solution { public int MaxPathSumHelper(TreeNode root, ref int globalMax) { if (root == null) return 0; int left = Math.Max(0, MaxPathSumHelper(root.left, ref globalMax)); int right = Math.Max(0, MaxPathSumHelper(root.right, ref globalMax)); int localMax = left + right + root.val; globalMax = Math.Max(globalMax, localMax); return Math.Max(left, right) + root.val; } public int MaxPathSum(TreeNode root) { int globalMax = int.MinValue; MaxPathSumHelper(root, ref globalMax); return globalMax; }}// Example usage:class Program { static void Main(string[] args) { TreeNode n1 = new TreeNode(-10); TreeNode n2 = new TreeNode(9); TreeNode n3 = new TreeNode(20); TreeNode n4 = new TreeNode(15); TreeNode n5 = new TreeNode(7); n1.left = n2; n1.right = n3; n3.left = n4; n3.right = n5; Solution sol = new Solution(); Console.WriteLine(“Maximum Path Sum: ” + sol.MaxPathSum(n1)); }} 6. JavaScript: class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; }}class Solution { maxPathSumHelper(root, globalMax) { if (!root) return 0; let left = Math.max(0, this.maxPathSumHelper(root.left, globalMax)); let right = Math.max(0, this.maxPathSumHelper(root.right, globalMax)); let localMax = left + right + root.val; globalMax[0] = Math.max(globalMax[0], localMax); return Math.max(left, right) + root.val; } maxPathSum(root) { let globalMax = [Number.NEGATIVE_INFINITY]; this.maxPathSumHelper(root, globalMax); return globalMax[0]; }}// Example usagelet n1 = new TreeNode(-10);let n2 = new TreeNode(9);let n3 = new TreeNode(20);let n4 = new TreeNode(15);let n5 = new TreeNode(7);n1.left = n2;n1.right = n3;n3.left = n4;n3.right = n5;let sol = new Solution();console.log(“Maximum Path Sum:”, sol.maxPathSum(n1)); Summary: