Leetcode | 第8节：记忆化搜索，树（上）
大家好！
今天我们来讲一讲记忆化搜索和树这个数据结构。记忆化搜索是对搜索算法的一个优化，涉及到记忆化搜索的题目都或多或少有一点技巧。至于树，它的定义非常简单，也有非常多的应用。同时它自己也在查找和排序中有自己的用武之地（例如二叉搜索树）。因此树的内容比较多也比较杂，我们可能没有办法一节给它说明白，也希望大家具备一些耐心～
那么我们开始吧。
记忆化搜索
记忆化搜索（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差别其实微乎其微。
数据结构6：树（上）
树是一个很有意思的数据结构，在很多时候都有重要的应用（例如文件索引）。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;
}
};
小结
这一节我们列了一些记忆化搜索的题目，并且再介绍了一些树相关的问题。可以看出树的问题也是各种各样，但大体上都和树的遍历，二叉搜索树，以及上一节提到的搜索方法有关。
当然，我们还没有完全的讲完树的题目，我们会在下一节再花一些功夫讲一下树的题目。如果还有空位的话，还会再讲一些需要一些数学知识的题目。