系统学习算法： 专题八 二叉树中的深搜
深搜其实就是深度优先遍历（dfs），与此相对的还有宽度优先遍历（bfs）
如果学完数据结构有点忘记，如下图，左边是dfs，右边是bfs
而二叉树的前序，中序，后序遍历都可以使用递归来编写，而这三种遍历都属于dfs
所以本质还是递归，只是换到了二叉树这个数据结构而已
题目一：
思路：
题意很简单，根据示例1所演示的很容易理解
那就是用递归去遍历
还是按照我们递归专题的方法，构想递归函数的功能，这道我希望递归函数能够我传入一个结点， 返回以我传入的这个结点为根的布尔值，所以参数是一个结点，然后无条件信任
找结束条件，那就是当结点为叶子结点时，是1返回true，是0返回false
然后是子问题的操作步骤
先通过调用递归函数拿到左子树的布尔值和右子树的布尔值，然后再看当前根结点是2还是3，是2就返回或的条件判断后的布尔值，是3就返回与的条件判断后的布尔值
代码：
class Solution {
//递归函数
public boolean dfs(TreeNode root){
//结束条件
if(root.left==null&&root.right==null){
return root.val==0?false:true;
}
//通过递归函数拿到左右子树的布尔值
boolean ret1=dfs(root.left);
boolean ret2=dfs(root.right);
//返回对应的条件判断后的布尔值
return root.val==2?ret1|ret2:ret1&ret2;
}
public boolean evaluateTree(TreeNode root) {
//调用递归函数
return dfs(root);
}
}所以这道题是一道后序遍历的dfs
题目二：
思路：
根据题意，以示例2为例子，我们得知在4这个结点，左子树应该返回495+491，右子树应该返回40，往下走，9这个结点，左子树应该返回95+91，0这个结点则返回0，5和1返回5，1
如果按照上面这么想的话，那么就走弯路了
因为4和9结点的子问题操作流程不一样，4返回495+491没问题，但是9不能返回95+91，和题意的意思无关，而且返回值只有一个，又怎么返回95，91两个返回值呢
所以这种从下往上的顺序是不对的
由此要换成从上往下的顺序，构想递归函数的功能是返回该结点的整条分支的和，这里功能要想清楚，比如9这个结点，应该返回495+491而不是95+91，是包含该结点的全部分支，5这个结点就应该返回495，1这个结点就应该返回491，按照这个逻辑，4就应该返回（495+491）+40，这样就符合题意了
所以要将该节点的父亲结点的值传下来，即9这个结点就应该拿到4这个参数，然后往下传49，5就会拿到49.这是就会返回495
结束条件就是左右结点都为空，即叶子结点时，就直接返回这条分支的和
代码：
class Solution {
public int dfs(TreeNode node,int presum){
//拿到并更新当前分支的前位数
presum=presum*10+node.val;
//如果是叶子结点
if(node.left==null&&node.right==null){
//返回该分支的和
return presum;
}
//左右分支的和
int ret1=0,ret2=0;
//如果有左分支
if(node.left!=null){
//返回左分支的和
ret1 = dfs(node.left,presum);
}
//如果有右分支
if(node.right!=null){
//返回右分支的和
ret2=dfs(node.right,presum);
}
//返回左右分支的和
return ret1+ret2;
}
public int sumNumbers(TreeNode root) {
//调用递归函数
return dfs(root,0);
}
}算比较难的一道题，因为很容易一开始陷入错误思路，想不到传参要传之前的数，越绕越迷糊
题目三：
思路：
题意就是删除全为0的子树，结束条件会比较好想一点，就是当为叶子结点的时候，如果是0就删除，不是0就保留，这里删除就用null来代替，所以上面的父结点会接收到空结点，如果左右子节点都返回空，那么这个父结点又成为新的叶子结点，由此递归的特征就体现出来了
代码：
class Solution {
public TreeNode dfs(TreeNode node){
//如果有左子树
if(node.left!=null){
//返回不包含1的子树
node.left=dfs(node.left);
}
//如果有右子树
if(node.right!=null){
//返回不包含1的子树
node.right=dfs(node.right);
}
//结束条件，如果为叶子结点，且为0
if(node.left==null&&node.right==null&&node.val==0){
//把自己删除掉
return null;
}else{
//不删除，返回自己
return node;
}
}
public TreeNode pruneTree(TreeNode root) {
root=dfs(root);
return root;
}
}题目四：
思路：
在学习二叉搜索树的时候，我们知道它有一个特点：那就是中序遍历的话它会返回一串有序的数组，由此我们就可以利用这个特点来解决这道题
我们可以设置一个全局变量，初始化为最小值，然后中序遍历二叉搜索树，每遍历到一个就与全局变量进行比较，如果大于，则说明到现在为止还是二叉搜索树，如果小于或等于，那就不是二叉搜索树
那我们这个递归函数的功能就是传入一个根节点，判断是否是二叉搜索树
结束条件就是当结点为空，就直接返回true，因为定义上空树也是二叉搜索树
注：底下提示有说数据范围最小为整型的最小值，所以全局变量要用long的最小值，避免刚好出现极端情况
代码：
class Solution {
//全局变量
long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
//空子树也是二叉搜索树
if (root == null) {
return true;
}
//先左
boolean left = isValidBST(root.left);
//再中
boolean cur = false;
//如果符合二叉搜索树的性质
if (root.val > prev) {
cur = true;
//更新变量
prev=root.val;
}
//后右
boolean right=isValidBST(root.right);
return left&&cur&&right;
}
} 其中如果判断完左子树如果已经不是二叉搜索树的话，我们就没必要继续了，就可以将剩下的“剪枝”掉，同理如果当前结点如果也不是二叉搜索树，右子树是不是二叉搜索树也无所谓了，也可以“剪枝”掉，而剪枝就是用if来判断一下就行
代码（剪枝）：
class Solution {
//全局变量
long prev = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
//空子树也是二叉搜索树
if (root == null) {
return true;
}
//先左（判断左子树是不是二叉搜索树）
boolean left = isValidBST(root.left);
//剪枝
if (left == false) {
return false;
}
//再中（判断当前结点是不是符合二叉搜索树）
boolean cur = false;
//如果符合二叉搜索树的性质
if (root.val > prev) {
cur = true;
//更新变量
prev=root.val;
}
//剪枝
if(cur==false){
return false;
}
//后右（判断右子树是不是二叉搜索树）
boolean right=isValidBST(root.right);
return right;
}
} 题目五：
思路：
这道题说了是二叉搜索树，所以还要利用中序遍历是有序的数组来解决，用一个全局变量count来记录遍历到第几个了，比如让count==k，每遍历一次count--，如果当count==0时，就说明当前结点的val就是第k小的元素，再用一个全局变量来保存该结点的值即可，然后剩下就全部return，可以用剪枝来优化，就判断一下保存答案的全局变量ret是否有值，如果有值就剪枝，没值就继续
代码：
class Solution {
int count=0;
int ret=0;
public int kthSmallest(TreeNode root, int k) {
count=k;
dfs(root);
return ret;
}
public void dfs(TreeNode root){
//为空就无事发生，顺便剪枝
if(root==null||ret!=0){
return;
}
//先左
dfs(root.left);
//每遍历一个就--
count--;
//如果是第k小的值，记录答案
if(count==0){
ret=root.val;
}
//如果已经找到答案了，剪枝
if(ret!=0){
return;
}
dfs(root.right);
}
}题目六：
思路：
这里就是前序遍历，因为是先处理完当前结点，再来考虑左右子树
一共有两种情况：叶子结点和非叶子节点
如果是叶子结点，就只用添加当前结点的值即可，并且将该字符串添加到list里
而如果是非叶子结点，那么不仅要添加当前结点的值，还要在后面多添加个“->”，但不添加到list
其中需要注意的是“恢复现场”
因为根据前序遍历的顺序，左结点之后才是右结点，所以字符串会先保留左结点的结果，比如上图会保留到1->2->4 ，但是回溯的时候，右边的结点应该是1->2->5->7，如果不恢复现场，就会是
1->2->45->7，导致左结点的结果影响了右结点
因此要注意恢复现场，如果是字符串是全局变量，那么操作就比较麻烦，要添加后再删除，我们可以利用函数参数来做到恢复现场，如果参数是String这种不可变对象就可以直接使用，因为是新创建一个String，但如果使用StringBuffer这种可变对象就不能直接使用，要自己在函数体中手动创建一个新StringBuffer
代码：
class Solution {
//保存所有路径的顺序表
List<String> list=new ArrayList<String>();
//使用StringBuffer作为参数
public void dfs(TreeNode node,StringBuffer s){
//需要手动创建一个新StringBuffer
StringBuffer str=new StringBuffer(s);
//先自身，如果为叶子结点
if(node.left==null&&node.right==null){
//就只加该结点的值
list.add((str.append(node.val)).toString());
//剪枝
return;
}
//不是叶子结点就加值和箭头
str.append(node.val+"->");
//再左
if(node.left!=null){
dfs(node.left,str);
}
//后右
if(node.right!=null){
dfs(node.right,str);
}
}
public List<String> binaryTreePaths(TreeNode root) {
StringBuffer str=new StringBuffer("");
dfs(root,str);
return list;
}
}总结：
如果遇到二叉树，那么大部分都要用到递归，也就是深搜（dfs），其中包括全局变量的使用，剪枝，回溯，而如果出现回溯，那么就会出现恢复现场，而出现递归就会出现回溯，也就是说递归就会涉及到恢复现场，其中二叉搜索树的特性是中序遍历后是有序的数组，操作顺序要结合题目来选择，是前序还是中序还是后序，接下来一些较难的题主要都会涉及到路径，路径最重要的也是恢复现场，所以要理解恢复现场