Leetcode | 第9节：树（下），数学题选摘
大家好！
这一节我们会继续上一节的最后，考虑树相关的问题。并且按照计划，我们会讲一些可能会考察到的数学题。
那么我们开始吧。
数据结构6：树（下）
Problem 1: Leetcode 226 翻转一棵二叉树。
假如说拿到的一棵二叉树是[4, 2, 7]，那么反转之后就是[4, 7, 2]，每一层都按照与原来相反的顺序排列。具体这个链表到底对应什么样的树，我们在上一节已经给过样例，读者可以参考上一节内容。
这个题目比较简单，翻转的目的其实就是左子树变成右子树，右子树变成左子树，所以本质上也是递归的思想。我们直接给出代码，不多做解释了。
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->left = right;
root->right = left;
return root;
}
};
Problem 2: Leetcode 117 给定一个二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。
举个例子，假如说我们的树是[1,2,3,4,5,null,7]，那么输出就是[1,#,2,3,#,4,5,7,#]，对应的是下面这张图。
本题也是比较容易的一个题。题解中的两个方法都是我们之前的章节所提到过的，所以我们也可以拿来做个复习。
第一个方法是层序遍历。层序遍历就是BFS的天下，简单来说，我们每一次都遍历一层，然后在这一层的元素内，从左到右建立链表，思路也比较直接。
那么我们看看代码吧。
class Solution {
public:
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
queue<Node*> q;
q.push(root);
while (!q.empty()) {
int n = q.size();
Node *last = nullptr;
for (int i = 1; i <= n; ++i) {
Node *f = q.front();
q.pop();
if (f->left) {
q.push(f->left);
}
if (f->right) {
q.push(f->right);
} // BFS的过程
if (i != 1) {
last->next = f; // 链表连接的过程
}
last = f;
}
}
return root;
}
};
第二个方法的话，是根据上一层的结果，来推断下一层。因为一层的next节点全部设置完之后，通过一层的初始节点，就能够遍历一层的所有节点了。这样就可以代替上一节所用到的队列，不需要一次把一层的节点都存储完，省去一些空间。
那我们具体来看看，在代码层面上如何实现这个步骤。
class Solution {
public:
void handle(Node* &last, Node* &p, Node* &nextStart) { // 这里传递的都是地址，也就是说在这个函数内部改变具体的值，返回之后是会影响的。
if (last) {
last->next = p;
}
if (!nextStart) {
nextStart = p;
}
last = p;
}
Node* connect(Node* root) {
if (!root) {
return nullptr;
}
Node *start = root;
while (start) {
Node *last = nullptr, *nextStart = nullptr;
for (Node *p = start; p != nullptr; p = p->next) { // 遍历上一层的所有节点，以寻找下一层节点的状态和
if (p->left) {
handle(last, p->left, nextStart); // 先观察节点的左子树，如果存在的话，考虑连next并且更新last与nextStart状态。
}
if (p->right) {
handle(last, p->right, nextStart); // 再观察节点的右子树，做类似的操作。
}
}
start = nextStart;
}
return root;
}
};
Problem 3: Leetcode 1110 给出二叉树的根节点 root，树上每个节点都有一个不同的值。 如果节点值在 to_delete 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。 返回森林中的每棵树。你可以按任意顺序组织答案。
比如说root = [1,2,3,4,5,6,7], to_delete = [3,5]。那么这个时候输出应该就是[[1,2,null,4],[6],[7]]，因为删完之后的森林就变成了这样。
可以看出，这棵树被拆分为了三棵独立的树。
对于这个问题，应该如何解决呢？其实比较需要思考的是，对于一个节点来说，删去它会影响哪些子树。不难想的是，一会影响到上面的一层（与它直接相连的父节点），二会影响到下面的一层（左右子树）。但是在这里，我们要注意的是，删去这一个节点之后，不会使得它父节点所相连的树的状态发生影响，但是会影响它的左右子树，具体来说，假如你删掉了右子树，那么必然这个节点的左子树和父亲不可能会被影响，它们都还在一棵树上对吧？
因此如果是这样的话，其实情况就简单了。我们不断的递归，遇到了需要删除的节点的时候，就把它的左右子树的内容分别添加到新的答案集合中。因为分别添加的目的就是在说明，这两个子树已经被拆分成了两棵树了，符合我们的题意。
好的，我们来看看代码吧。
class Solution {
private List<TreeNode> forest;
private Set<Integer> dict;
public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
forest = new ArrayList<>();
dict = new HashSet<>();
for (int t : to_delete) {
dict.add(t);
}
root = helper(root);
if (root != null) {
forest.add(root);
} // 将没有受到影响的部分再添加进去。读者可以想想，为什么只需要添加一开始的根节点所对应的这一棵树，不会有遗漏吗？
return forest;
}
public TreeNode helper(TreeNode root) {
if (root == null) {
return root;
}
root.left = helper(root.left);
root.right = helper(root.right);
if (dict.contains(root.val)) {
if (root.left != null) {
forest.add(root.left);
}
if (root.right != null) {
forest.add(root.right);
} // 将目标节点的左右子树分别添加，相当于完成了拆分
root = null; // 删除节点
}
return root;
}
}
好的，关于树相关的问题我们就写这么多。需要提醒大家的是，我们的树相关的题目更多还是针对树本身的结构来挑选的高频题，然而不乏还有非常多的题目，是会结合其他已有的算法的。这样的题目就会具有更强的综合性，我们会在之后总结的时候再放出一部分这样的习题。
算法5：数学
数学题很难说是属于《算法与数据结构》的一部分，但是架不住面试官拿那么一两道这样的题目来恶心你……所以对于数学题，我们也会摘录一些高频题，也算是以防万一吧……
Problem 4: Leetcode 69 实现平方根函数
思路很简单，读者如果想了解二分查找可以看这一节，我们就不多解释了，直接放代码。
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
return ans;
}
};
好的，我们来看看代码吧。
class Solution {
public:
double quickMul(double x, long long N) {
if (N == 0) {
return 1.0;
}
double y = quickMul(x, N / 2); // 相当于制造出那个x^k
return N % 2 == 0 ? y * y : y * y * x; // 分奇偶讨论。
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
不过之前我们说过，因为递归需要额外的栈的空间，我们很多时候会考虑使用迭代法，会更好一些。但是这个题中，迭代法的分析不如递归那么自然。
怎么遍历二进制表达呢？其实只需要每一次让次幂对2取模。如果为1就说明这一位有贡献，然后不停的让次幂除以2就可以了（注意，这里的除以2是下取整的，和C++/Java内的规则相同）。
好的，我们来看看代码应该怎么写。
class Solution {
public:
double quickMul(double x, long long N) {
double ans = 1.0;
double x_contribute = x; // x^1
while (N > 0) {
if (N % 2 == 1) {
// 如果 N 二进制表示的最低位为 1，那么需要乘上
ans *= x_contribute;
}
x_contribute *= x_contribute; // x^1, x^2, x^4, x^8, ...
N /= 2;
}
return ans;
}
double myPow(double x, int n) {
long long N = n;
return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
}
};
这里我们建议大家两个方法都掌握，考察的频率还是很高的。
Problem 6: Leetcode 319 初始时有 n 个灯泡处于关闭状态。 对某个灯泡切换开关意味着：如果灯泡状态为关闭，那该灯泡就会被开启；而灯泡状态为开启，那该灯泡就会被关闭。 第 1 轮，每个灯泡切换一次开关。即，打开所有的灯泡。 第 2 轮，每两个灯泡切换一次开关。即，每两个灯泡关闭一个。 第 3 轮，每三个灯泡切换一次开关。 第 i 轮，每 i 个灯泡切换一次开关。而第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。
这一个问题属于典型的，想明白之后代码不超过五行的问题。当然，这确实也是部分数学题的独有特性。
好的，我们来看看代码吧。
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n+0.5);
}
};
额，没啥好说的，对吧？
Problem 7: Leetcode 357 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10^n 。
比方说输入是2的话，那么输出就是91，因为[0, 99]中，除了11到99这九个数以外，都是符合要求的。另外还可以看出来，事实上n最多也就是10.
class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
int fact[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int res = 0;
for (int i = 10-n; i <= 9; ++i) {
res += fact[9] / fact[i];
}
return res * 9 + 1;
}
};
Problem 8: Leetcode 264 给你一个整数
n，请你找出并返回第n个 丑数 。 丑数 就是只包含质因数2、3和/或5的正整数。
比方说如果n = 10，那么输出就是12，因为[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]是由前10个丑数组成的序列。
这是一个很经典的数学题，官方提供了两种方法，一个是动态规划，另一个则类似埃氏筛。为了给数学一点面子，我们这里主要提供埃氏筛的做法。
当然要注意的是，这里还需要去重的。你可以在输出的时候加一个额外判断，判断元素是否会有重复，重复的话就不记录了。你也可以直接将这个堆结构做成一个哈希结构，这样也可以。
好的，我们来看看代码吧。
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> factors = {2, 3, 5};
unordered_set<long> seen;
priority_queue<long, vector<long>, greater<long>> heap;
seen.insert(1L);
heap.push(1L);
int ugly = 0;
for (int i = 0; i < n; i++) {
long curr = heap.top();
heap.pop();
ugly = (int)curr; // 更新丑数。
for (int factor : factors) {
long next = curr * factor;
if (!seen.count(next)) {
seen.insert(next); // 另外维护了一个哈希结构，在判断如果有重复之后，就不再放到堆里了。
heap.push(next);
}
}
}
return ugly;
}
};
Problem 9: Leetcode 96 给你一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
比方说如果n = 3，那么输出就是5，五棵树的样子是这样的。
这一个问题看似不像是一个数学题，但是因为它涉及到一个卡特兰数的概念，所以我们拿来说一下。
当然了，如果单放卡特兰数的计算公式，估计说我是骗子的人会更多一点。所以我们先给出一个动态规划的方法，再放出卡特兰数的公式，这样在介绍的时候也会更自然一点。
因此也可以直接通过这个公式来编写程序。
class Solution {
public:
int numTrees(int n) {
long long C = 1;
for (int i = 0; i < n; ++i) {
C = C * 2 * (2 * i + 1) / (i + 2);
}
return (int)C;
}
};
Problem 10: Leetcode 150 根据 逆波兰表示法，求表达式的值。 有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
逆波兰表达式还有一个名字叫作后缀表达式。我们把它放到了数学这一个模块下，但本质上它就是一个栈实现四则运算的一个《算法与数据结构》的课后习题。
具体的做法我们这里直接给出。
- 如果遇到操作数，则将操作数入栈；
- 如果遇到运算符，则将两个操作数出栈，其中先出栈的是右操作数，后出栈的是左操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数入栈。
代码层面上也比较容易理解，按照这个算法逐步实现即可。
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
int n = tokens.size();
for (int i = 0; i < n; i++) {
string& token = tokens[i];
if (isNumber(token)) {
stk.push(atoi(token.c_str()));
} else {
int num2 = stk.top();
stk.pop();
int num1 = stk.top();
stk.pop();
switch (token[0]) {
case '+':
stk.push(num1 + num2);
break;
case '-':
stk.push(num1 - num2);
break;
case '*':
stk.push(num1 * num2);
break;
case '/':
stk.push(num1 / num2);
break;
}
}
}
return stk.top();
}
bool isNumber(string& token) {
return !(token == "+" || token == "-" || token == "*" || token == "/");
}
};
放出这个题的目的是，栈做四则运算也是一个很重要的考察点。
小结
本节相比较之前的内容来说，篇幅少了一些，题目层面上也没有太多可以分析的地方。这是因为一方面，很多数学题非常具有“想到就是想到，想不到就是想不到”的特点，另一方面，有一些与数组操作有关的数学相关的题目我们没有放到这一部分来说，而会放到之后的数组，字符串的模块，以及综合分析的模块再进行介绍。因此这一部分也算比较轻松～
下一节我们来介绍一些数组和字符串模块的综合题。我不知道该如何归类这两种题目，但是毫无疑问的是它们可以分出非常多小的tricks，也会用到我们之前已经介绍过的一些算法。当然，这也会是很大的一部分篇幅～