系统学习算法： 专题八 二叉树中的深搜

深搜其实就是深度优先遍历（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);}//结束条件，如果为叶子结点，且为0if(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){//需要手动创建一个新StringBufferStringBuffer 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），其中包括全局变量的使用，剪枝，回溯，而如果出现回溯，那么就会出现恢复现场，而出现递归就会出现回溯，也就是说递归就会涉及到恢复现场，其中二叉搜索树的特性是中序遍历后是有序的数组，操作顺序要结合题目来选择，是前序还是中序还是后序，接下来一些较难的题主要都会涉及到路径，路径最重要的也是恢复现场，所以要理解恢复现场