Divide and Conquer

• $T(n)=aT(\dfrac{n}{b})+f(n)$ can be used to analyze the complexity of divide-and-conquer methods.
  • $f(n)$ 可以代表 divide 跟 combine 所花費的時間。

有兩種序，就有機會還原出唯一一棵二元樹。比方說，只知道 preorder 和 inorder ，求出原本的二元樹。

應用

• 在 Tree traversal 中，只知道 preorder 和 inorder ，要求出原本的二元樹。（參考 DS/Tree）