二叉树和分治算法总结

• • 分治法能够处理的问题
  • 代码注意事项
  • 时间复杂度分析
  • 题目汇总

1. 大问题可以拆分成更小规模的问题。
2. 每个子问题互相独立，一个子问题的解不会对另一个子问题的解造成影响。
3. 当子问题规模特别小的时候，可以直接得到答案的情况。
4. 子问题的解可以合并成原有问题的解。

当上述所有条件都满足，才能使用分治法处理。

分治法使用递归来实现，在递归的使用中要明确递归的三要素：

1. 递归的定义——递归函数的返回值、参数要如何定义。
2. 递归的拆解——递归如何向下拆分成更小规模的问题。
3. 递归的出口——递归的结束条件。

分治法使用的递归有两种形式：遍历形式和分治形式，遍历的形式相当于走遍所有的路径亲自计算结果，分治的形式相当于将任务往下派发获取结果进行组合。

遍历和分治两种形式的区别：遍历（Traverse）使用全局变量或者引用类型的参数来处理结果，分治使用返回值来处理结果。具体可以参看题14。

常规二叉树和分治法的时间复杂度，其中节点操作的的时间复杂度为O(1)，相当于每次在O(1)的耗时内将大问题的拆分成两个规模只有一半的问题，总时间复杂度计算如下：

T(n) = 2 * T(n/2) + O(1)
     = 2 * (2*T(n/4) + O(1)) + O(1)
     = 4 * T(n/4) + 2 * O(1) + O(1)
     = 4 * (2*T(n/8) + O(1)) + O(1)
     = 8 * T(n/8) + 4 * O(1) + 2 * O(1) + O(1)
     = n * T(n/n) + O(n/2 + n/4 + …… + 1)
     = O(n) + O(n)
     = O(n)

复杂二叉树和分治法的时间复杂度，其中节点操作的的时间复杂度为O(n)，相当于每次在O(n)的耗时内将大问题的拆分成两个规模只有一半的问题，总时间复杂度计算如下：

T(n) = 2 * T(n/2) + O(n)
     = 2 * (2*T(n/4) + O(n/2)) + O(n)
     = 4 * T(n/4) + 2*O(n/2) + O(n)
     = 4 * (2*T(n/8) + O(n/4)) + 2*O(n/2) + O(n)
     = 8 * T(n/8) + 4*O(n/4) + 2*O(n/2) + O(n)
     = n * T(n/n) + O(n) + O(n) + …… + O(n)
     = O(n) + logn*O(n)
     = O(n * log n)

注意与二分搜索算法的时间复杂度计算区分，二分搜索每次会折半问题的规模，但分治法每次只是拆分问题规模，拆分出来的两个问题之后还是需要分别解决的。
二分搜索算法总结：https://blog.csdn.net/SeeDoubleU/article/details/124361813

14. 二叉树的前序遍历（Binary Tree Preorder Traversal）https://blog.csdn.net/SeeDoubleU/article/details/119834420
15. 二叉树的中序遍历（Binary Tree Inorder Traversal）https://blog.csdn.net/SeeDoubleU/article/details/119943283
16. 二叉树的后序遍历（Binary Tree Postorder Traversal）https://blog.csdn.net/SeeDoubleU/article/details/120446191
17. 归并排序（Merge Sort）https://blog.csdn.net/SeeDoubleU/article/details/121153020
18. 快速排序（Quick Sort）https://blog.csdn.net/SeeDoubleU/article/details/122421967
19. 二叉树的最大深度（Maximum Depth Of Binary Tree）https://blog.csdn.net/SeeDoubleU/article/details/124361881
20. 找出二叉树的所有路径（Binary Tree Paths）https://blog.csdn.net/SeeDoubleU/article/details/124361905
21. 结点之和最小的子树（Minimum Subtree）https://blog.csdn.net/SeeDoubleU/article/details/124361940
22. 最近共同先祖（Lowest Common Ancestor of a Binary Tree）https://blog.csdn.net/SeeDoubleU/article/details/124362003
23. 二叉树中的最长连续序列（Binary Tree Longest Consecutive Sequence）https://blog.csdn.net/SeeDoubleU/article/details/124362013
24. 二叉树的路径和（Binary Tree Path Sum）https://blog.csdn.net/SeeDoubleU/article/details/124362029