（十二）算法设计思想之“分而治之”

分而治之是是什么

分而治之是算法设计中的一种方法
它将一个问题分成多个和原问题相似的小问题，递归解决小问题，再将结果合并以解决原来的问题
应用场景：归并排序、快速排序、二分搜索、翻转二叉树…

场景一：归并排序

分：把数组从中间一分为二
解：递归地对两个子数组进行归并排序
合：合并有序子数组

场景二：快速排序

分：选基准，按基准把数组分成两个子数组
解：递归地对两个子数组进行快速排序
合：对两个子数组进行合并

LeetCode：374.猜数字大小

解题思路
二分搜索，同样具备“分、解、合”的特性
考虑选择分而治之

解题步骤
分：计算中间元素，分割数组
解：递归地在较大或者较小子组件进行二分搜索
合：不需要此步，因为在子数组中搜到就返回了

时间复杂度O(logn)，空间复杂度是O(logn)

LeetCode：226.翻转二叉树

解题思路
先翻转左右子树，再将子树换个位置
符合“分、解、合”特性
考虑选择分而治之
解题步骤
分：获取左右子树
解：递归地翻转左右子树
合：将翻转后的左右子树换个位置放在根节点上

时间复杂度O（n），n是树的节点数，空O（树的高度），最坏的情况是O（n）

LeetCode：100.相同的树

解题思路
两个树：根节点的值相同，左子树相同，右子树相同
符合“分、解、合”特性
考虑选择分而治之
解题步骤
分：获取两个树的左子树和右子树
解：递归地判断两个树的左子树是否相同，右子树是否相同
合：将上述结果合并，如果根节点的值也相同，树就相同

时间复杂度O(n),n是树的节点数，空间复杂度最坏情况是O（n），好的情况是O(logN)

LeetCode：101.对称二叉树

解题思路
转化为：左右子树是否镜像
分解为：树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
符合“分、解、和”特性，考虑选择分而治之
解题步骤
分：获取两个树的左子树和右子树
解：递归地判断树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
合：如果上述都成立，且根节点值也相同，两个树就镜像

时间复杂度O(n),n是树的节点数，空间复杂度最坏情况是O（n），好的情况是O(logN)

思考题

1、说出分而治之算法的套路步骤
2、用分而治之的套路步骤，描述切西瓜的过程，无需Coding