Solving Algorithmic Problems

Description   Solution: Post-Order DFS Post-order DFS to get the size of each child subtree. Use a hashset to keep track of how many different subtree sizes there are, if the hashset has more than one element, then the tree is not good. Time Complexity:  O(n) Space Complexity:  O(n) function countGoodNodes ( edges ) { let n = edges.length + 1 ; let graph = Array (n).fill( 0 ).map( () => []); for ( let [a, b] of edges) { graph[a].push(b); graph[b].push(a); } let good = 0 ; dfs( 0 , - 1 ); return good; function dfs ( node, parent ) { let sizes = new Set (), size = 1 ; for ( let nei of graph[node]) { if (nei === parent) continue ; let neiSize = dfs(nei, node); sizes.add(neiSize); size += neiSize; } if (sizes.size <= 1 ) good++; return size; } };

Description   Solution: Post-order DFS Choose one node value to keep per leaf node path. Use post-order DFS to find the minimum sum of node values taking one node per path (at the end, the result is  total sum - dfs(0, -1) ) For each  dfs(node) , we have two choices: Take the node: We get to keep all the subtree values except the current node. Skip the node: Each child subtree needs to choose one value to keep. n = number of nodes ,  m = number of edges Time Complexity:  O(n + m) Space Complexity:  O(n + m) var maximumScoreAfterOperations = function ( edges, values ) { let n = values.length, graph = Array (n).fill( 0 ).map( () => []); for ( let [a, b] of edges) { graph[a].push(b); graph[b].push(a); } let totalSum = values.reduce( ( sum, value ) => sum + value); return totalSum - dfs( 0 , - 1 ); function dfs ( node, parent ) { if (graph[node].length === 1 && graph[node][ 0 ] === parent) { return va...

Description   Solution: DFS Key point: For each node, the sum of the all children paths must be equal since they share the same root path. Since we can only increase node values, we must make all path sums equal to the maximum path sum. Increase the child node with the smaller path sum to become equal to the larger path sum. Then, return the maximum out of the left and right path sums. n = number of nodes ,  h = height of tree Time Complexity:  O(n) Space Complexity:  O(h) var minIncrements = function ( n , cost ) { let ans = 0 ; dfs ( 1 ) ; return ans ; function dfs ( i ) { if ( i * 2 > n ) return cost [ i - 1 ] ; // leaf node let leftSum = dfs ( 2 * i ) , rightSum = dfs ( 2 * i + 1 ) ; ans += Math . max ( leftSum , rightSum ) - Math . min ( leftSum , rightSum ) ; return cost [ i - 1 ] + Math . max ( leftSum , rightSum ) ; } } ;