分治
nothing-sy2023-11-14算法 分治策略
TIP
一个问题是否适合使用分治解决，通常可以参考以下几个判断依据。
- 问题可以分解：原问题可以分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
- 子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决。
- 子问题的解可以合并：原问题的解通过合并子问题的解得来。 显然，归并排序满足以上三条判断依据。
类似于二分查找，归并排序，快速排序等都符合分治策略。
在这一节中，会讲解一个构建树的典型例子，来理解分治策略。
:::题目：
给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder ，请从中构建二叉树，返回二叉树的根节点。假设二叉树中没有值重复的节点。
:::
分析：
原问题定义为从 preorder 和 inorder 构建二叉树，是一个典型的分治问题。
1. 问题可以分解：从分治的角度切入，我们可以将原问题划分为两个子问题：构建左子树、构建右子树，加上一步操作：初始化根节点。而对于每棵子树（子问题），我们仍然可以复用以上划分方法，将其划分为更小的子树（子问题），直至达到最小子问题（空子树）时终止。
2. 子问题是独立的：左子树和右子树是相互独立的，它们之间没有交集。在构建左子树时，我们只需关注中序遍历和前序遍历中与左子树对应的部分。右子树同理。
3. 子问题的解可以合并：一旦得到了左子树和右子树（子问题的解），我们就可以将它们链接到根节点上，得到原问题的解
WARNING
关于构建树的思路在这里有详解：https://www.hello-algo.com/chapter_divide_and_conquer/build_binary_tree_problem/#3