二叉树中的深搜

一)计算布尔二叉树的值

2331. 计算布尔二叉树的值 - 力扣（LeetCode）

1)计算布尔二叉树需要从叶子节点向上进行计算，从下向上进行计算

2)完整二叉树是同时拥有左孩子和右孩子，或者是完全没有右孩子

3)当我只是盯着根节点来看的时候，此时我想知道我这一层的结果是什么？必须先知道这个根节点的左子树的布尔值，还需要知道右子树的布尔值，当我知道左右子树是true或者是false的时候，在我这一层把左右子树的信息整合；

4)如果想要知道左子树或者是右子树是true还是false，这不是恰好和我们的大问题是一样的吗？主问题就是解决这棵树是true还是false

5)重复子问题函数头:给定一个指针，判断以这个指针为结点的树是true还是false，求以这个节点为根节点的boolean值

6)函数体:先知道左子树是true还是false，再知道右子树是true还是false最后在本层进行整合

boolean flag1=dfs(root.left)；

boolean flag2=dfs(root.right)；

return root.val==2?flag1orflag2:flag1&flag2

7)递归出口:遇到叶子节点，只需要将叶子节点是true还是false返回

8)本质上这个题就是在做一个后序遍历，本质上就是一个深度优先遍历，先返回左节点的boolean值，再返回右节点的boolean值，最后再根据根结点的值进行计算，在遇到叶子节点的时候，将叶子节点的信息返回到上一层
class Solution {public boolean evaluateTree(TreeNode root) {if(root==null) return true;if(root.left==null&&root.right==null) return root.val==0?false:true;
//先进行计算左子树的boolean值boolean flag1=evaluateTree(root.left);
//再进行计算右子树的booleanboolean flag2=evaluateTree(root.right);return root.val==2?flag1|flag2:flag1&flag2;}
}

二)求根节点到叶子节点数字之和

129. 求根节点到叶节点数字之和 - 力扣（LeetCode）

1)二叉树的递归问题想一下递归到某一层的时候要干什么事情，当遍历到某一个根节点所干的事情都一样的时候，况且干这个事情能够得到最终我所想要的结果，那么这个这个事情就是相同子问题，当我们遍历到某一个根节点的时候，还是需要将这个跟跟节点的左子树之和和右子树之和计算相加返回给上一层

2)此时我们需要进行计算的点就是当遍历到某一个根节点的时候，需要知道前面的数字的信息，就比如说遍历到5的时候是需要知道12的信息的，因为当前我遍历到这一层的时候我什么也不知道，我怎么计算出1258呢？我只是知道当前根节点以及后续节点的信息，根本不知道当前根节点以前的信息

3)知道12的信息之后，再结合当前根节点进行计算出125的值，然后再将125传递给它的左子树和右子树，算出左右子树的值，最后将对应的值返回给根节点，在进行相加，返回到上一层节点

第一步:知道前面的数是12之后，进行计算当前结点的值是125

第二步:将当前的这个125传递给以5为根节点的左子树，算出左子树的和是1258

第三步:将这个125传递给以5为根节点的右子树，计算出右子树的和是XXXX

第四步:将左子树和右子树返回的和进行相加，最后返回当前根节点的上一层

1)函数头的设计:你给我传入一个根节点之后，把以这个根节点相连的左右子树叶子之和进行返回，int dfs(Node root，int k)参数是当前传入的根节点和你传递到这个根节点的时候，从原始根节点到这个递归层次的结点的路径和，传入一个根节点，计算出以当前根节点的所有叶子节点之和进行返回

2)函数体:执行1 2 3 4步

3)递归出口:递归出口是在第二步进行执行的
class Solution {public int GetSum(TreeNode root,int k){//根据题目给定的数据范围来说不可能出现根节点的情况//遍历到叶子结点的时候才到了递归结束的出口if(root.left==null&&root.right==null){return root.val+k*10;}int current=k*10+root.val;int ret=0;//算出左子树的和if(root.left!=null) ret+=GetSum(root.left,current);//算出右子树的和if(root.right!=null) ret+=GetSum(root.right,current);//返回值是左子树和右子树的和return ret;}public int sumNumbers(TreeNode root) {return GetSum(root,0);}
}

三)二叉树剪枝:

814. 二叉树剪枝 - 力扣（LeetCode）

1)在这个问题中子问题就是给定一个头指针，将以这个头指针为根节点的所有为0的子树全部干掉，返回最后处理结果的头指针

2)当给定一个头结点的信息的时候，我必须知道以当前根节点的左子树的信息和以当前根节点的右子树的信息，必须是左子树全为0或者是右子树全为0，我才可以将左子树或者是右子树剪掉，所以需要后序遍历，因为只有出现后序遍历的时候，才能带着左子树的信息和右子树的信息；

3)进行模拟递归的过程:从叶子节点开始判断，通过决策树模拟删除递归的这样一个过程即可

1)当判断完左子树之后，我需要继续进行判断右子树也就是0的右节点，此时发现右节点的左子树和右子树也都是空，况且右节点的值也是0，所以右节点也是可以干掉的，但是此时返回到1的时候虽然发现左节点和右节点都是空，但是发现当前根节点是1，所以不能干掉

2)接下来继续判断0的右节点

3)函数体:先处理左子树，再进行处理右子树，再来处理当前节点

4)函数出口:root=null
class Solution {//给定一个根节点,返回左子树和右子树简直之后的头节点public TreeNode pruneTree(TreeNode root) {if(root==null) return null;root.left=pruneTree(root.left);
//返回左子树剪枝之后的结果,将左子树中是0的分支全部干掉,返回处理完成之后的左根节点root.right=pruneTree(root.right);
//返回右子树剪枝之后的结果,将右子树是的0的分支全部干掉,返回处理之后的右根节点//判断当前位置是否需要剪枝,如果发现左右子树都为空，况且当前节点是0,那么直接返回即可if(root.left==null&&root.right==null&&root.val==0){return null;}else{return root;}}
}

四)验证二叉搜索树

98. 验证二叉搜索树 - 力扣（LeetCode）

之前我的做题思路就是说先进行判断一下以当前节点为根节点的左子节点和右子节点是一颗二叉搜索树，再进行判断当前根节点的左子树是否是一颗二叉搜索树，和当前根节点的右子树是否是一颗二叉搜索树没但是这个判断方法是错误的，只能通过72个测试用例，请看上面

解法1:根据中序遍历的结果来判断这颗树是否是二叉搜索树
class Solution {public List<Integer> GetList(TreeNode root){Stack<TreeNode> stack=new Stack<>();List<Integer> list=new ArrayList<>();while(!stack.isEmpty()||root!=null){while(root!=null){stack.push(root);root=root.left;}TreeNode node=stack.pop();list.add(node.val);root=node.right;}return list;}public boolean isValidBST(TreeNode root) {List<Integer> list=GetList(root);for(int i=0;i<list.size()-1;i++){if(list.get(i)>=list.get(i+1)) return false;}return true;}
}
解法2:递归

1)首先定义一个全局变量，prev=-00，这个全局变量的意思就是在中序遍历的过程中，当进行遍历到某一个位置的时候，它的中序遍历到此位置的前驱是多少，所以仅仅需要将当前位置的节点和它的前驱节点prev进行判断一下即可，prev的作用就是当进行中序遍历到某一个节点的时候，它的前驱的值是多少；

2)剪枝:就比如说在下面这个节点中，当我遍历到19这个位置的时候发现prev=20，此时就可以直接判断这棵树不是一个二叉搜索树了，那么应该此时直接停止中序遍历，直接向上返回false，当我们在深度优先遍历的过程中，发现某一个分支绝对不存在想要的结果的时候，在本题中发现这个分支不需要在进行遍历了，如果这个分支特别长，就可以剪掉很多枝叶了，就可以加快我们的搜索过程，就是为了避免深度优先遍历一些没有意义的东西

3)左子树是一颗二叉搜索树，当前节点也是符合二叉搜索树的定义，右子树也是一颗二叉搜索树， 根据当前节点如何来进行判断呢，只需要和prev作比较即可，无序和后面的数进行比较，因为和后面的数作比较的过程中序遍历已经帮助我完成了
class Solution {long prev=Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root==null) return true;
boolean flag1=isValidBST(root.left);//先把判断左子树是否是一颗二叉搜索树boolean flag3=true;if(root.val<=prev) flag3= false;prev=root.val;
boolean flag2=isValidBST(root.right);//判断右节点是否是一颗二叉搜搜书return flag1&&flag2&&flag3;//如果左子树满足二叉搜索树定义,右子树满足二叉搜索树定义,况且根节点也满足二叉搜锁树定义,直接返回true}

五)二叉搜索树中第k小的元素

230. 二叉搜索树中第K小的元素 - 力扣（LeetCode）

两个全局变量+中序遍历:

使用一个全局变量count，count=k，当k最终减到0的时候，使用另一个全局变量ret来保存最终返回的结果
class Solution {int ret=0;int count=0;public int kthSmallest(TreeNode root, int k) {count=k;dfs(root);return ret;}public void dfs(TreeNode root){if(root==null) return;dfs(root.left);count--;if(count==0){ret=root.val;}dfs(root.right);}
}