postorder merge

instead of building the result, as we go down, we build it POST order as in after the rec step

this is very similar to DP except since you are only dependent on children states you usually optimise globally and return NEEDED state

problems

• maximum path sum on a binary tree f(u) → max path starting from u and optimises a global max

• binary tree cameras *** this one was nicer, you do a greedy but the KEY idea here was that when dp seems to account for parent — instead of thinking children of children try to add ONE more state to the child ( to account for children of children )

edge case I got wrong: A → B → C,D now by somestuff ABOVE A, say that A needs to be marked, then you don’t skip B just because it is covered ( as that would mark both C and D )

• max sum bst in a bin tree this is MORE of a reprsentative problem for this topic

  10 5 12 I got the bst property wrong initially and assumed u just need 5 and is 5 subtree a BST, above case shows clearly that that alone is not enough.

it’s almost a dp no?

well in the case of a tree you MERGE child states and NEVER really visite them again so technically you can just SKIP the whole dp array as long as the return is the FULL substates of a node for example f(node, state1, state2,…) the dfs post order must return all the states at once

so you can do like auto child = {} for c: children ⇒ child.append(dfs(to get child state))

^ this is the portorder bit

and then you just process similarly

technically I think that EVERY problem can be postorder but it’s just often easier to solve it as a dp with a state vector and so

problems — more on the dp end

• vertex cover ⇒ min set of nodes such that all edges have some end in the set
  • note that an optimal solution CAN have adjacent nodes ⇒ 1 = 2 = 3 = 4
• kingdom division ⇒ this more dp like really, 2 color a tree such that EACH colored components has size >= 2
• anniversay party ⇒ similar as above ones really, nothing new