10. 二叉搜索树中第 k 小的元素
题目链接：
题目描述：
题目示例：
解法：中序遍历 + 计数器剪枝
算法思路：
上述解法不仅使用大量额外空间存储数据，并且会将所有的结点都遍历一遍。但是，我们可以根据中序遍历的过程，只需扫描前 k 个结点即可。因此，我们可以创建一个全局的计数器 count，将其初始化为 k，每遍历一个节点就将 count--。直到某次递归的时候，count 的值等于 0，说明此时的结点就是我们要找的结果。
C++ 算法代码：
/**
* 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 count, ret = 0;
int kthSmallest(TreeNode* root, int k) {
count = k;
dfs(root);
return ret;
}
void dfs(TreeNode* root) {
if(root == nullptr || count == 0) {
return;
}
dfs(root->left);
if(--count == 0) {
ret = root->val;
return;
}
dfs(root->right);
}
};
算法总结及流程解析：
11. 二叉树的所有路径
题目链接：
题目描述：
题目示例：
解法：回溯
算法思路：
使用深度优先遍历 (DFS) 求解。路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加入到路径中，如果该节点为叶子节点，将路径存储到结果中。否则，将 "->" 加入到路径中并递归遍历该节点的左右子树。
定义一个结果数组，进行递归。递归具体实现方法如下:
- 如果当前节点不为空，就将当前节点的值加入路径 path 中，否则直接返回；
- 判断当前节点是否为叶子节点，如果是，则将当前路径加入到所有路径的存储数组 path 中;
- 否则，将当前节点值加上 "->" 作为路径的分隔符，继续递归遍历当前节点的左右子节点；
- 返回结果数组。
特别地，我们可以只使用一个字符串存储每个状态的字符串，在递归回溯的过程中，需要将路径中的当前节点移除，以回到上一个节点。
C++ 算法代码：
/**
* 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:
// 用全局变量 ret 记录所有路径，全局不会受到递归回溯的影响
vector<string> ret;
vector<string> binaryTreePaths(TreeNode* root) {
string path; // 用局部变量 path 记录路径的值，不用全局变量是为了便于回溯时'恢复原状'
dfs(root, path);
return ret;
}
void dfs(TreeNode* root, string path) {
// 递归的结束条件：当前结点为空则结束递归进行返回
if(root == nullptr) {
return;
}
// 当遇到叶子结点时则不用再添加箭头，并且此时一条路径已经结束，
// 用 string 数组 ret 进行记录并且直接返回
if(root->left == nullptr && root->right== nullptr) {
path += to_string(root->val);
ret.push_back(path);
return;
}
// 前序遍历
path += to_string(root->val);
path += "->";
dfs(root->left, path);
dfs(root->right, path);
}
};
算法总结及流程解析：
