大家好!
今天我们来讲一讲记忆化搜索和树这个数据结构。记忆化搜索是对搜索算法的一个优化,涉及到记忆化搜索的题目都或多或少有一点技巧。至于树,它的定义非常简单,也有非常多的应用。同时它自己也在查找和排序中有自己的用武之地(例如二叉搜索树)。因此树的内容比较多也比较杂,我们可能没有办法一节给它说明白,也希望大家具备一些耐心~
那么我们开始吧。
记忆化搜索(Memorization)是搜索算法的一个改进。简单来说就是,对于搜索中的状态,如果可以保存下来,那么在之后的搜索中,遇到相同的状态就可以直接返回对应的结果,而不用再递归搜索,造成重复运算。大家可以看出来,这一点其实和动态规划非常像。是的,记忆化搜索可以理解为是动态规划的一个前身,但是它的思考方式是从“搜索”发源而来,而动态规划更多是需要思考状态转移方程怎么写,在思维上是有差异的。关于动态规划的内容,读者可以查看这两节
好的,那么我们来看几道记忆化搜索的习题吧。
Problem 1: Leetcode 140 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。
比方说如果输入s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]
,那么输出就是
[
"cats and dog",
"cat sand dog"
]
可以看出,这确实是仅有的对于这个句子拆分的两种可能。
如果使用上一节的方法,其实也很好想,就是从前到后遍历,每一次选择一段进行拆分(比方说对于样例数据,我们可以通过遍历拆分出cat
和cats
)。那么在这里,其实就有几个优化点。第一就是,我们拆分出来的单词到底是不是我们的单词列表内的,这就需要去比较。那么如果和单词列表内的单词一个个去比,就会很浪费时间。所以这一步,其实可以把列表中的单词都放到一个哈希表内,这样查找的时候就是
的时间复杂度了。
当然了,这肯定不是记忆化搜索的部分。记忆化搜索顾名思义,是要保存一些状态,避免重复计算。这里可以保存的状态就是从某一个位置出发到之后,可以组成的句子列表。因为如果保存了这个信息,在到达某一个位置之后,就可以通过这个信息,来减少之后的运算。
具体怎么实现这一步的,我们来通过代码说明。
class Solution {
private:
unordered_map<int, vector<string>> ans; // 记录答案,表示从第一个下表i开始的,分拆的句子list
unordered_set<string> wordSet;
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
wordSet = unordered_set(wordDict.begin(), wordDict.end()); // 将list放到一个哈希表(set)内,用于减少判断次数。
backtrack(s, 0);
return ans[0];
}
void backtrack(const string& s, int index) {
if (!ans.count(index)) { //如果答案在这个位置没有记录过结果才会继续下一步的迭代,如果已经有记录过结果,则会直接返回。
if (index == s.size()) {
ans[index] = {""};
return;
}
ans[index] = {};
for (int i = index + 1; i <= s.size(); ++i) {
string word = s.substr(index, i - index);
if (wordSet.count(word)) {
backtrack(s, i); //判断是否有word,有的话,就继续回溯
for (const string& succ: ans[i]) {
ans[index].push_back(succ.empty() ? word : word + " " + succ); // 先判断word之后的位置是否已经保存过一些答案,如果保存过的话,将它们的之前都拼上单词word,就是一组新的句子了。
}
}
}
}
}
};
这一个过程有点类似动态规划的思路,即从一个规模最小的,解确定的子问题出发,一步步推广到大问题的解。例如对于样例数据,比较清楚的就是最后三个字母一定只有可能是一个dog
,不可能有其它可能的拆分方法,那么之后的结果就是基于此拓展得到的。读者可以通过递归树来进一步明晰这个过程。
Problem 2: Leetcode 329 给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。
例如说matrix = [[9,9,4],[6,6,8],[2,1,1]]
,那么输出就是4。这对应着下面这一张图
对于这个问题,想到DFS是不难的,每一次走的时候都观察一下相邻的单元格,哪一个是具有上升趋势的,再走到下一个格子继续递归。但是这样很明显的问题在于,每一个点都会有自己固定的最长递增路径,但是传统的搜索会导致重复计算,每一个点都会遍历多次。因此有个方案,就是每一个点的最长路径都事先保存一下,这样再一次走到这个点的时候,就可以直接返回正确的结果。
好的,我们来看看代码吧。同样,我们会在代码中标记,哪里使用了记忆化搜索。
class Solution {
public:
static constexpr int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 记录四个方向
int rows, columns;
int longestIncreasingPath(vector< vector<int> > &matrix) {
if (matrix.size() == 0 || matrix[0].size() == 0) {
return 0;
}
rows = matrix.size();
columns = matrix[0].size();
auto memo = vector< vector<int> > (rows, vector <int> (columns));
int ans = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < columns; ++j) {
ans = max(ans, dfs(matrix, i, j, memo));
}
}
return ans;
}
int dfs(vector< vector<int> > &matrix, int row, int column, vector< vector<int> > &memo) {
if (memo[row][column] != 0) { // 记忆化搜索
return memo[row][column];
}
++memo[row][column];
for (int i = 0; i < 4; ++i) {
int newRow = row + dirs[i][0], newColumn = column + dirs[i][1];
if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[row][column]) {
memo[row][column] = max(memo[row][column], dfs(matrix, newRow, newColumn, memo) + 1); // 递归的同时保存结果,最后返回memo的结果即可。
}
}
return memo[row][column];
}
};
Problem 3: Leetcode 403 一只青蛙想要过河。假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。青蛙可以跳上石子,但是不可以跳入水中。 给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。 开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2 )。 如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k - 1、k 或 k + 1 个单位。另请注意,青蛙只能向前方(终点的方向)跳跃。
如果输入是stones = [0,1,3,5,6,8,12,17]
,那么输出就是true
。因为可以采用的方案是:跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后,跳 5 个单位到第 8 个石子(即最后一块石子)。
这一道题的标准做法是动态规划,但是用记忆化搜索也是可以解决的,我们来看一看应该怎么做。
可以使用记忆化搜索,是因为它本身是可以通过搜索算法进行求解的。那么这里可以记忆化的地方就在于两个状态,一个是青蛙所处的石子位置,一个是青蛙上一次的跳跃距离。当固定了这两个状态之后,之后的解就是确定的(因为就固定了青蛙下一步只能走的步数了)。
好的,我们通过代码来看看,如何把这个记忆化搜索的步骤融入进去。
class Solution {
public:
vector<unordered_map<int, int>> rec;
bool dfs(vector<int>& stones, int i, int lastDis) {
if (i == stones.size() - 1) {
return true;
}
if (rec[i].count(lastDis)) { // 观察是否已经记录过这个状态(记忆化搜索),i表示位置,lastDis表示上一次的跳跃距离
return rec[i][lastDis];
}
for (int curDis = lastDis - 1; curDis <= lastDis + 1; curDis++) {
if (curDis > 0) {
int j = lower_bound(stones.begin(), stones.end(), curDis + stones[i]) - stones.begin(); // 找到可以跳跃的石子,读者可以思考一下为什么使用lower_bound函数
if (j != stones.size() && stones[j] == curDis + stones[i] && dfs(stones, j, curDis)) {
return rec[i][lastDis] = true;
}
}
}
return rec[i][lastDis] = false;
}
bool canCross(vector<int>& stones) {
int n = stones.size();
rec.resize(n); // 规定二维map的第一个维度大小为n
return dfs(stones, 0, 0); // 初始状态,一开始的位置为0,一开始没有走,所以上一次的距离自然也是0
}
};
所以大家可以看出来,记忆化搜索的关键其实就在于寻找状态,并记录状态。代码整体与DFS差别其实微乎其微。
树是一个很有意思的数据结构,在很多时候都有重要的应用(例如文件索引)。Leetcode中对于树相关的问题考察的也尤其多,所以估计很明显,也是需要我们多花时间来总结总结的。
关于树的定义,我们这里略去不提(毕竟这个不会的话可能先看看《算法与数据结构》更好),直接来看题目。
Problem 4: Leetcode 104 给定一个二叉树,找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
比方说输入的二叉树是[3,9,20,null,null,15,7]
,那么输出就是3
。因为它对应的二叉树长下面这样。
涉及到树相关的问题,我们都会有专门的数据结构来描述树。因此这一题我们放出树的样子,在之后就不再重复画图了。
这一题本质上就是一个极为简单的DFS。你只需要不停的往左或者往右走,然后最大的深度就取决于下面的子树的深度再加1。
好的,我们来看看代码吧。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
没什么好说的,充其量熟悉一下树的结构。
Problem 5: Leetcode 110 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
平衡二叉树的定义都不是很陌生,所以只需要计算它左右子树的深度再判断是否符合条件即可。因此如果使用DFS,代码可以写的非常简单,我们直接给出。
class Solution {
public:
int height(TreeNode* root) {
if (root == NULL) {
return 0;
} else {
return max(height(root->left), height(root->right)) + 1;
}
}
bool isBalanced(TreeNode* root) {
if (root == NULL) {
return true;
} else {
return abs(height(root->left) - height(root->right)) <= 1 && isBalanced(root->left) && isBalanced(root->right);
}
}
};
既然这么简单就描述完了,那么为什么要放出来这一个题呢?这是因为对于这一道题,其实可以通过降低遍历次数来达到优化的目的的。注意到对于这一个方法,本质上就是先计算,再遍历height的左右两边,再回头进行判断,是二叉树中的先序遍历方法。但是事实上,在先序遍历算法中,一个高度为
的节点,对应的它的
个祖先都会调用到这一节点的height方法上,本质上就会产生重复计算。所以优化的法子就是,在每一个节点,先遍历height的左右两边,再判断是否平衡,这相当于后序遍历。后序遍历的话,不会在一开始就给出节点的高度差的计算结果,而是到达最后的时候才进行计算。一定程度上可以使得在计算父节点的结果的时候,可以利用上之后后序遍历中,子节点已经计算过的结果。
后序遍历的代码大概长这个样子。
class Solution {
public:
int height(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1) {
return -1;
} else {
return max(leftHeight, rightHeight) + 1;
}
}
bool isBalanced(TreeNode* root) {
return height(root) >= 0;
}
};
可以看出,我们是先保存了height
计算的结果(先左右遍历),再进行的判断。
Problem 6: Leetcode 236 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”各个节点的元素各不相同。
如果输入为root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
,那么输出就是3
,因为3
是5
和1
的公共祖先。
对于这个问题,首先要想明白的是,什么是公共祖先?对于树的问题,绝大部分都是需要通过递归,把问题化归到子树上来做。这个题也一样,我们可以通过左右子树是否含有
节点,来进一步判断是否它是公共祖先。
对于一棵子树,如果它的根节点是
,那么如果
就是
中的一个,那么另外一个必须也要在
的左右两棵子树中。如果都不是,那么必须
的左右两棵子树必须一个为
,一个为
。有的人可能会说,会不会出现
,然后它的左右子树也确实有一个有
中的一个,**但是不是
而是
。**这个不可能,因为各个节点的元素各不相同。
这里还有人会问,就是会不会出现
都在一边的情况,且都不是根节点本身。这一点可以观察一下,如果是这个情况,那么这一个节点一定不会是最深的节点,读者可以想一想为什么。
总结一下,可以写出这样的判断式
最后还有一个细节,就是,如何判断是最近的公共祖先呢?这里其实可以观察到的点是,在这个条件下,假如说我们找到了一个满足条件的公共祖先,并且做了标记,那么可以发现的是,在这个条件下,没有其他的节点可以再同时满足这个条件(因为假定了这个节点下面只有一个
节点或者
节点,所以就不可能再找到其它符合条件的了)。
好的,我们来放出代码。
class Solution {
public:
TreeNode* ans;
bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) return false;
bool lson = dfs(root->left, p, q);
bool rson = dfs(root->right, p, q);
if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
ans = root;
}
return lson || rson || (root->val == p->val || root->val == q->val);
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
dfs(root, p, q);
return ans;
}
};
Problem 7: Leetcode 437 给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
比方说如果输入是root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
,那么输出就是3
,对应的3条路径如下。
对于这个问题,可以使用的处理方案就是前缀和。因为这里的路径没有一个明确的起点和终点,但是根据题目要求,任何一条路径都可以分解为两个路径和的差,并且两条路径的起点都是根节点。我们画一张图看一下。
基于此,我们就可以考虑通过前缀和来求解相关问题。
好的,我们来看一看代码吧。
class Solution {
private:
unordered_map<int, int> prefix; // <前缀和,其出现次数>
void dfs(TreeNode* root, int sum, int cur_sum, int& res)
{
if (!root) return;
cur_sum += root->val; // 更新前缀和
// 当前路径中存在以当前节点为终点的和为sum的子路径
if (prefix.find(cur_sum - sum) != prefix.end())
res += prefix[cur_sum - sum];
prefix[cur_sum]++; // 将当前节点加入路径
dfs(root->left, sum, cur_sum, res);
dfs(root->right, sum, cur_sum, res);
prefix[cur_sum]--; // 状态还原
}
public:
int pathSum(TreeNode* root, int sum)
{
int res = 0; // 满足条件的路径数量
prefix[0] = 1; // 前缀和为0的路径只有一条:哪个节点都不选
dfs(root, sum, 0, res);
return res;
}
};
这里记录一个res表示满足条件的路径数量,是因为很明显,一个前缀和不可能只会唯一的对应一个元素。
Problem 8: Leetcode 230 给定一个二叉搜索树的根节点
root
,和一个整数k
,请你设计一个算法查找其中第k
个最小元素(从 1 开始计数)。
这一道题涉及到的就是二叉搜索树(Binary Search Tree)相关的问题。简单来说,二叉搜索树就是左子树的元素都比它小,右子树的元素都比它大。当然,它还有一个很重要的性质,就是中序遍历是升序排列。
知道这个之后,其实问题就明确了。我们给这棵二叉搜索树跑一次中序遍历,返回第
个元素即可。所以如果使用递归,代码极为简单,我们直接给出。
class Solution {
public ArrayList<Integer> inorder(TreeNode root, ArrayList<Integer> arr) {
if (root == null) return arr;
inorder(root.left, arr);
arr.add(root.val);
inorder(root.right, arr);
return arr;
}
public int kthSmallest(TreeNode root, int k) {
ArrayList<Integer> nums = inorder(root, new ArrayList<Integer>());
return nums.get(k - 1);
}
}
这一题使用的是Java,不过把它换成C++其实改动也不会很大。
但这一个题我们还希望给出一个迭代做的方法。在很多时候,如果递归的栈容量不够,碰巧树又不平衡,就会容易出现栈溢出的错误。所以适当了解一下模拟栈结构的迭代做法,很多时候也是面试中很重要的加分点。
那么我们看一下迭代法的代码有哪些细微的区别。
class Solution {
public int kthSmallest(TreeNode root, int k) {
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
while (true) {
while (root != null) {
stack.add(root);
root = root.left;
}
root = stack.removeLast();
if (--k == 0) return root.val;
root = root.right;
}
}
}
可以看出,这里入栈就相当于进入下一次递归,出栈就相当于之前的判断条件,函数的返回。
关于如何将树的遍历的递归程序转为迭代法,可以参考下面这一篇文章。
https://zhuanlan.zhihu.com/p/257329741
一个类似的题目是Leetcode 173,99。读者可以根据这个题目题解中的递归法和迭代法,进一步理解树的遍历。
Problem 9: Leetcode 450 给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。 一般来说,删除节点可分为两个步骤: 首先找到需要删除的节点;如果找到了,删除它。说明:要求算法时间复杂度为 O(h),h 为树的高度。
这一个问题还是有些难度的,我们来看一下如何建模。
首先还是那句话,二叉搜索树的中序遍历就是数组的升序排列。因此如果我们删去了一个节点,为了保证它其它节点的顺序不变,我们在替代节点的时候,必须要用它的前驱或者后继节点中的一个来进行替代(想想为什么?)。并在替代之后想办法恢复树的结构。
那么如果要做到这一步,首先就要熟悉《数据结构》中的前缀和后缀二叉树的构造方法。在这里,就是对应中序遍历的前缀和后缀,这些我们之后会直接给出代码。读者如果不明白的话,需要在《数据结构》中寻找对应的章节进行学习。
对于一个要删除的节点,它一共只有四种情况:叶子结点,只有左子树,只有右子树,左右子树均有。这四种情况中,右子树其实可以处理“左右子树均有”的情况,因为它可以直接用它的后继节点来进行替代(相当于递归,走一步就到了)。在这个情况下,修改起来就不会太困难。考虑到这一个题只需要给出一种方案,我们不用再花心思做四种情况的分类了。
当然,你用前驱节点替代也行,没人拦着你。
好的,分开考虑。如果这是一个叶子结点,那直接删除就好。读者容易发现,这样子不会改变原有的结构。如果它有右子树,那么这个时候,我们考虑用它的后继节点进行替代。具体来说,就是
对于第三种情况,就是节点只有左子树没有右子树,那么这个时候就自然考虑用前驱节点进行替代。方法是类似的,无非就是后继节点变成了前驱节点,“从右子树出发”变成了“从左子树出发”而已。
好的,我们来看看代码吧。
class Solution {
public int successor(TreeNode root) {
root = root.right;
while (root.left != null) root = root.left;
return root.val;
}
public int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) root = root.right;
return root.val;
}
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key > root.val) root.right = deleteNode(root.right, key);
else if (key < root.val) root.left = deleteNode(root.left, key); // 递归向下找到要删除的节点。
else {
if (root.left == null && root.right == null) root = null;
else if (root.right != null) {
root.val = successor(root);
root.right = deleteNode(root.right, root.val); // 用后继节点进行替换,并且在右子树那里删除掉这个后继节点。
}
else {
root.val = predecessor(root);
root.left = deleteNode(root.left, root.val); // 用前驱节点进行替换,并且在左子树那里删除掉这个前驱节点。
}
}
return root;
}
}
这里的successor
和predecessor
分别对应了寻找前驱和后继节点的代码。可以看出,它们只是中序遍历做了一步的结果。
这里还有一个细节,就是读者可以看出,我们是使用递归的方式来删除前驱和后继节点的。这是因为,deleteNode函数本身目的就是删除节点,并且维持二叉搜索树的结构。所以如果它有右子树,那么我们就只需要把它的后继节点粘贴过来,然后“向右走一步,递归,删除这个后继节点,并维持二叉搜索树的结构“。可以看出,引号里的这一句话,其实要做的事情和deleteNode
函数本身是相同的(毕竟右子树也是树,也要维持二叉搜索树的结构),因此倒也不必说思考下一步怎么办,直接递归就完事了。
Problem 10: Leetcode 109 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
对于这一个题,读者肯定也都清楚了,二叉搜索树要搞成升序排列,直接中序遍历就完事了。但这里还多了两个坎,一个是链表,一个是“高度平衡”。所以还是有一些思考空间的。
这里首先留一个悬念,就是如果我们取中位数(注意如果这里元素个数是偶数,那么不是取二者的中间值,而是取中间两个的任意一个作为中位数。定义上略有不同)作为二叉树的根节点,那么得到的树一定是平衡的。按照这个写法,我们其实可以做的事情就是:通过中序遍历,将对应位置的节点填入不同的地方,然后边进行遍历边完成构造。
具体的做法大概可以写成这样
好的,我们来看看代码是怎么写的。
class Solution {
public:
int getLength(ListNode* head) {
int ret = 0;
for (; head != nullptr; ++ret, head = head->next);
return ret;
}
TreeNode* buildTree(ListNode*& head, int left, int right) {
if (left > right) { // 递归发现这个区间已经没有位置了,那么直接返回空节点
return nullptr;
}
int mid = (left + right + 1) / 2; // 中位数
TreeNode* root = new TreeNode();
root->left = buildTree(head, left, mid - 1);
root->val = head->val;
head = head->next;
root->right = buildTree(head, mid + 1, right); // 中序遍历的顺序
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
int length = getLength(head);
return buildTree(head, 0, length - 1);
}
};
可以看出,中序遍历的时候,相当于先确认了中位数,然后再分为左右两半。左右两半分别对应不同的根节点(一个head
一个head->next
)。
最后我们来证明一下这个方法的准确性。
现在假设链表的长度为
,对应的二叉搜索树的高度为
。那么容易发现
。
现在我们使用归纳法,假如
的时候,二叉搜索树都是平衡的,也就是说,
,都有
(这是我们构造方法所决定的假设)。那么
的时候。分两种情况考虑,如果
,那么左右子树大小为
,左右两边的二叉搜索树的高度都应该是
,所以
。
的时候,左边是
右边是
,所以因为
,符合假设,所以也是二叉搜索树。综上所述,不管奇数偶数,都是二叉搜索树,这就证明了结论。
Problem 11: Leetcode 103 给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
比方说如果输入[3,9,20,null,null,15,7]
,那么输出就是
[
[3],
[20,9],
[15,7]
]
这一题其实就是二叉树的层序遍历,但是稍微加了一点技巧,就是如果第一层是从左到右遍历的,第二层就需要从右往左遍历。
回忆一下层序遍历,我们一直都是使用BFS来完成。每一次遍历一层,把一层一层的结果放到队列中。那么在这里,因为顺序要不断地变,所以我们要使用的数据结构就是双端队列。简单来说,大概就是,如果从左往右遍历,那么就按照正常的队列方式,从尾部插入。否则的话,就从头部插入即可。
好的,我们来看看代码是什么样的吧。
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (!root) { // 枚举到了最后的节点
return ans;
}
queue<TreeNode*> nodeQueue;
nodeQueue.push(root);
bool isOrderLeft = true; // 记录状态,简单来说,记录应该插入尾部还是头部。
while (!nodeQueue.empty()) {
deque<int> levelList;
int size = nodeQueue.size();
for (int i = 0; i < size; ++i) {
auto node = nodeQueue.front();
nodeQueue.pop();
if (isOrderLeft) { // 观察这一层的状态。
levelList.push_back(node->val);
} else {
levelList.push_front(node->val);
}
if (node->left) {
nodeQueue.push(node->left);
}
if (node->right) { // BFS过程
nodeQueue.push(node->right);
}
}
ans.emplace_back(vector<int>{levelList.begin(), levelList.end()});
isOrderLeft = !isOrderLeft; // 到下一层的时候,true变成false
}
return ans;
}
};
这一节我们列了一些记忆化搜索的题目,并且再介绍了一些树相关的问题。可以看出树的问题也是各种各样,但大体上都和树的遍历,二叉搜索树,以及上一节提到的搜索方法有关。
当然,我们还没有完全的讲完树的题目,我们会在下一节再花一些功夫讲一下树的题目。如果还有空位的话,还会再讲一些需要一些数学知识的题目。