目录
1.验证二叉搜索树
题解
2.二叉搜索树中第K小的元素
题解
3.二叉树的所有路径
题解
1.验证二叉搜索树
链接：98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数。
- 节点的右子树只包含 大于 当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
关于什么是搜索二叉树，可以看这篇前文~15. 【C++】详解搜索二叉树 | KV模型
题解
这道题主要想说的有三个方面 1. 全局变量的优势 ，2. 回溯 ，3. 剪枝
这里我们利用一个性质，二叉搜索树的中序遍历结果，是一个有序的序列
- 可能你会想到用一个数组记录中序遍历的结果，然后在遍历一下数组。但是这样空间开销太大了。
我们还是利用这个性质解决这个问题，但是我们可以仅用一个全局变量就来判断这个中序遍历是否是有序的。
- 这个全局变量是在中序遍历中当我遍历到某一个位置它的前序是多少。
- 并且因为是全局的，并不需要考虑在递归中如何传递，直接拿过来用就可以了
当中序遍历到第一个节点后，比较该值和prev的大小，当前这个值比无穷小大说明当前中序遍历是有序的，就更新prev等于这个值。
- 然后向上传，同理依旧是拿这个值和prev做比较等等，知道中序遍历到19发现这个值比prev要小，此时中序遍历就不是有序的
- 说明30左子树就不一颗二叉搜索树，也说明20右子树不是一颗二叉搜索树，进而说明整棵树就不是一颗二叉搜索树。
- 直接返回即可！
所以这道题我们可以 借助全局变量和中序遍历 就可以解决这个问题。
- 我们有两种策略判断它是否是一个二叉树。
策略一：
- 左子树是一颗二叉搜索树，
- 当前节点也要符合二叉搜索树的定义
- 右子树也是一颗二叉搜索树
此时就颗树就是一颗二叉搜索树！
一个 递归99%都有回溯，往上层返回就是回溯！
当前节点值的范围正好有INT_MIN
- 如果我们prev=INT_MIN 有可能第一层判断就有问题。
- 因此把prev类型换一下，long 或者 long long
class Solution {
public:long prev = LONG_MIN;//判断遍历反条件情况
//还可以实现剪枝bool isValidBST(TreeNode* root) {if(!root) return true;if(!isValidBST(root->left)) return false;if(root->val <= prev) return false;prev = root->val;if(!isValidBST(root->right)) return false;return true;}
};- 当判断某棵子树不是二叉搜索树，整体就已经不是二叉搜索树了，就没有必要在去其他子树递归了，直接返回结果就行了。
- 例如说 上面的举例，遍历到 18 之后，就可以 return 啦
- 加快了我们的搜索过程
剪枝其实很简单，不要想的那么复杂。
2.二叉搜索树中第K小的元素
链接：230. 二叉搜索树中第K小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。
题解
有了上面题的基础，这道题就非常简单了，仅需 两个全局变量 count ret +中序遍历 就行了
- 每次count-1，直到count==0
- 用ret记录结果。
- 找到最终结果此时其他子树也不用遍历。也可以使用剪枝。
如果不使用全局变量，就需要在递归函数中传参，并且还需要考虑参数在递归函数中如何改变
class Solution {
public:int ret=0;int count;int kthSmallest(TreeNode* root, int k) {count=k;dfs(root); //分离 实现单纯的遍历return ret;}void dfs(TreeNode* root){if(!root) return;dfs(root->left);if(--count==0){ret=root->val; //存储结果return;//剪枝 结束}dfs(root->right);}
};3.二叉树的所有路径
链接：257. 二叉树的所有路径
题解
- 题目很简单，让找根到叶子节点的所有路径。
这道题重点强调的还是
- 全局变量
- 回溯
- 剪枝
其中这道题最重要的是想说 回溯 ----> “恢复现场”
只要记住，因为出现了回溯 才会想到要 恢复现场
- 只要出现递归必定会有回溯，既然回溯中有恢复现场
- 那就可以这样说，只要有深度优先遍历就有恢复现场的操作。
- 只不过在简单题恢复现场这个动作并不明显，因为 参数在递归过程中就已经自动恢复现场了，但是在一些难的题里面，一旦用到全局变量，我们要手动恢复，这个恢复现场操作就会变成额外重要。
比如这道题我们用两个全局变量
- path是把根到叶子节点所经历的路径记录下来
- ret是把path到叶子节点后的整条路径记录下来。
path遇到不是叶子节点就 值 + ->，遇到叶子就把path放到ret数组中。
但是此时有一个超级致命的问题，回溯的时候，path要回到上一层，你会发现回溯到上一层path不应该有 4 的，因为path往其他子树传仅需要传 1->2-> 就行了！
- 那此时就应该 恢复现场，把全局变量恢复下去之前的样子。
- 此时还有一个问题如果把path设计成全局变量，回溯时path要不停pop，从叶子节点回溯还好说，但是从非叶子节点回溯要pop两次，挺麻烦的！
这道题用全局变量path记录路径比较麻烦，仅是这道题全局path不好用
- 但是比较麻烦的题全局path好用
- 这里只是为了说明，有对于 path 恢复现场这个操作的。
这道题我们函数头这样设计 void dfs(root,path)，把path当成参数传给函数，你会发现恢复现场特别容易，函数特性就已经帮我们恢复现场了。
- 因为每次函数都会重新创建一个path，回溯到上一层用的还是上一层自己的path~
- 就不用自己手动恢复了。
总结一下：全局变量 不好手动 恢复现场，那就 参数 自动 恢复现场
函数头，函数体都差不多了，接下来就是递归出口了
- 当root == nullptr 返回。
- 但是这里递归还要进去才返回。此时我们可以剪枝，当非空进去，空就不要进！
- if(root->left ==nullptr&& root->right ==nullptr)
class Solution {
public:vector<string> ret;vector<string> binaryTreePaths(TreeNode* root) {string path="";dfs(root,path);return ret;}void dfs(TreeNode* root,string path){path+=to_string(root->val);if(!root->left && !root->right){ret.push_back(path);return;}path+='-';path+='>';//path参数 是已经存入 每一层了，会自动恢复的。if(root->left) dfs(root->left,path);if(root->right) dfs(root->right,path);}
};
