今日的每日一题来一个leetcode题目， 《105. 从前序与中序遍历序列构造二叉树》
题目描述：
```
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \\
9 20
/ \\
15 7
```
题目链接： https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
题解：思路：
利用中序把数组划分成左右两个，定出左右子树在中序中的左右界（这里用到哈希表）。前序就好办，挨个遍历就好。有个tricky的地方，就是要保存前序目前处理到哪里了
代码：
```C++
class Solution {
private:
int pos = 0;
private:
TreeNode* genTree(vector& pre, unordered_map& m, int s, int e) {
if (pos >= pre.size() || s > e) return nullptr;
auto root = new TreeNode(pre[pos++]);
if (s == e) return root;
int loc = m.find(root->val)->second;
root->left = genTree(pre, m, s, loc - 1);
root->right = genTree(pre, m, loc + 1, e);
return root;
}
public:
TreeNode* buildTree(vector& preorder, vector& inorder) {
auto m = unordered_map();
for (auto i = 0; i < inorder.size(); ++i) {
m.insert(make_pair(inorder[i], i));
}
return genTree(preorder, m, 0, inorder.size() - 1);
}
};
```
可以是三进制么？二进制有什么好处？题解：为什么叫电子计算机？算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系？深度优先遍历的范围更大还是回溯的范围更大？为什么？题解：我的理解是：dfs是回溯思想的一种体现- 回溯：是在整个搜索空间中搜索出可行解，在搜索过程中不断剪枝回退，这是回溯的思想，这个搜索空间并没有限制于特定的数据结构。- dfs：dfs是指特定的数据结构中如图，树（特殊的图）中搜索答案，范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜，八对袜子的布质、大小完全相同，而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢？题解：暴力破解， 把袜子都拆开 一人一只 哈哈
LeetCode题解分鸡块外卖鸡块分别有 4，6，12 块， 每 固定块数不能分开装， 用户给一个数字， 要求返回满足用户订单（可以等于也可以大于）的最少的盒数的组合
LeetCode题解10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。10个小球，随机分到12个盒子里，求恰好10个盒子都为空的概率。要求用程序模拟十万次，暴力求出该概率来自：字节跳动 算法工程师一面的第一题 （3月30日，60分钟，牛客网视频面）https://www.nowcoder.com/discuss/395924