分治法，顧名思義就是分而治之，即把問題拆解爲性質相同的小問題再處理。下面小編爲大家整理了PHP算法學習之分治法，希望能幫到大家！
做了一些題後發現，分治法除了分治，名字裏還少了一步，那就是合，也就是怎樣通過小問題的答案得到拆分之前大問題的答案。
分治法的時間複雜度：分治法並沒有像二分法一樣每次丟掉一半無用的解，它只是做了分離，而分離的兩部分都是需要處理的，所以分治法的時間複雜度是O(n)。特例情況是當分離的兩部分繼續分治處理出現重複計算的情況時，就會比O(n)大了！所以請確保你的分治儘量不要出現重疊計算的情況。
那麼什麼問題適合用分治的思想解決呢？二叉樹！二叉樹這種左右子樹的結構天生就非常適合分治，所以它的大部分問題都能用分治解決，碰到一個問題你只需要問問左子樹你怎麼處理，右子樹你怎麼辦，得到左右子樹的答案後，你再想想最後的答案是個啥~除了二叉樹，快速排序歸併排序這兩個著名的排序算法也是分治的思想。下面就舉幾個解題的'例子來加深一下對分治法的學習。
1、前序遍歷二叉樹
2、求二叉樹的最大路徑和
給一棵二叉樹，找出從根節點出發的路徑中，和最大的一條。
這條路徑可以在任何二叉樹中的節點結束，但是必須包含至少一個點。
3、求最近公共祖先
給定一棵二叉樹，找到兩個節點的最近公共父節點(LCA)，給出的兩個節點都在樹中存在。
4、快速排序
這裏我就偷個懶，直接貼出百度百科上給的php標準答案~
