力扣2331.计算布尔二叉树值
深度搜索：是要进入最下面
二叉树直接往递归上去想（易写，不易想）
public boolean evaluateTree(TreeNode root) { if(root.left==null||root.right==null){ return root.val==0?false:true; } //先拿到左子树，然后返回 boolean left=evaluateTree(root.left); //再拿到右子树，然后返回 boolean right=evaluateTree(root.right); //从根部开始走 return root.val==2?left|right:left&right; }
力扣129.求根节点到叶子节点数字之和
这道题的思路，我是没想出来，然后看视频教
怎么说从上面走到下面，再从下面回归到上面
public int sumNumbers(TreeNode root) { return dfs(root,0); } public int dfs(TreeNode root,int preSum){ //及时更新结果第一步，把当前值传递给下一个递归的 preSum=preSum*10+root.val; if(root.left==null&&root.right==null){ return preSum; } int sum=0; // if(root.left!=null) sum=sum+dfs(root.left,preSum); if(root.right!=null) sum=sum+dfs(root.right,preSum); return sum; }
力扣814.二叉树剪枝
public static TreeNode pruneTree(TreeNode root) { if(root.left==null&&root.right==null){ if(root.val==0){ root=null; } return root; } if(root.left!=null) { root.left=pruneTree(root.left);} if(root.right!=null) { root.right = pruneTree(root.right); } if(root.left==null&&root.right==null&&root.val!=1){ return null; } return root; }
这几个递归，已经能摸索出来一点东西，假如两边都是null，还要记得判断他的值，假如他是0，才可以让他是空，然后判断叶子结点之后，我们也要判断，假如他作为根节点，需不需要判断呢？答案也是必然的，所以当根的左右都为空，根也是0，那么这个根也可以返回null。
力扣98.验证二叉搜索树
我自己的思路开始肯定不是知道什么中序遍历，刚开始我是想要去递归，但是发现这个函数类型是boolean,但是boolean这个类型，我不能根据这个返回TreeNode,那么也就是说我不能通过递归的结果比较数值，那么我就想再去定义一个函数（类型TreeNode)，暂时思路是这样，但是没有写出来。原因：
开始的想法：这个是错误的，看下面图片，作者说的很清楚，不可以这么写
public boolean isValidBST(TreeNode root) { if (root == null) return true; if (root.left != null && root.val <= root.left.val || root.right != null && root.val >= root.right.val) return false; return isValidBST(root.left) && isValidBST(root.right); } 作者：数据结构和算法 链接：https://leetcode.cn/problems/validate-binary-search-tree/solutions/441173/san-chong-jie-jue-fang-shi-liang-chong-ji-bai-liao/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
二叉搜索树中序遍历的结果，是一个有序的序列
1.全局变量的优势
2.回溯：递归之后的返回值，就叫回溯（牛马，一点不高级）
3.剪枝：当发现不是二叉搜索树的时候，就没有必要管其他节点（意义是加快搜索过程）
策略一：左子树是二叉搜索树，当前节点符合二叉搜索树的定义，右子树也是二叉搜索树。（关注自己怎么判断，只需要和prev做判断即可，无需和后面这些数做比较，因为和后面这些数做比较的过程中序遍历已经完成了。）
策略二：剪枝，当找到不符合的情况，直接返回false即可。
引入一个知识：
class Solution { //-231 <= Node.val <= 231 - 1,他有可能拿这种数字恶心你，所以你设置一个最小的，那么也就是Long类型的最小值 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; //剪枝的思想。就是简单的不用考虑一些东西 if(cur==false) return false; prev=root.val; boolean right=isValidBST(root.right); return left&&cur&&right; }
中序遍历：左根右（左树节点小于根，根小于右边节点）
思路：因为中序遍历之后，是一个有序的，所以我们只需要保证按照中序遍历，保存他的前一个值，然后用前一个值和他比较，就可以比较出是true，还是false。
遍历左树的时候，还是看左树是true还是false,怎么看，看左树的节点跟他的前一个值比较，假如比他大，那么就返回真。假如是假，那么就说明树不是二叉搜索树，然后更新前一个值，让前一个值等于当前值，再看他的右子树，右子树是开始和根节点比较，（根节点和最后一个左叶子结点比较）
