## 前言

`二叉树的递归分为「遍历」和「分解问题」两种思维模式，这道题可以同时用到两种思维模式。 「遍历」的话很简单，你对 BST 做中序遍历，其结果就是有序的，重新构造出题目要求的这个类似链表的二叉树即可。`

## 一、力扣113. 路径总和 II

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if(root == null){
return new ArrayList<>();
}
fun(root,targetSum,0);
return res;
}
public void fun(TreeNode root,int targetSum, int sum){
if(root == null){
return;
}
if(root.left == null && root.right == null){
if(sum + root.val == targetSum){
}
path.remove(path.size()-1);
return;
}
fun(root.left,targetSum,sum+root.val);
fun(root.right,targetSum,sum+root.val);
path.remove(path.size()-1);
}
}
``````

## 二、力扣1430. 判断给定的序列是否是二叉树从根到叶的路径

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
int len = 0;
boolean flag = false;
public boolean isValidSequence(TreeNode root, int[] arr) {
len = arr.length-1;
fun(root,arr,0);
return flag;
}
public void fun(TreeNode root, int[] arr , int index){
if(root == null || index > len){
return;
}
if(root.val == arr[index]){
if(index == len && root.left == null && root.right == null){
flag = true;
}
fun(root.left,arr,index+1);
fun(root.right,arr,index+1);
}
return;
}
}
``````

## 三、力扣897. 递增顺序搜索树

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
TreeNode pre = null, first = null;
boolean flag = true;
public TreeNode increasingBST(TreeNode root) {
fun(root);
pre.left = null;
pre.right = null;
return first;
}
public void fun(TreeNode root){
if(root == null){
return;
}
fun(root.left);
if(pre != null){
pre.right = root;
pre.left = null;
}
pre = root;
if(flag){
first = root;
flag = false;
}
fun(root.right);
}
}
``````

## 四、力扣938. 二叉搜索树的范围和

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
int sum = 0;
public int rangeSumBST(TreeNode root, int low, int high) {
fun(root,low,high);
return sum;
}
public void fun(TreeNode root, int low, int high){
if(root == null){
return ;
}
if(root.val > high){
fun(root.left,low,high);
}else if(root.val < low){
fun(root.right,low,high);
}else{
sum += root.val;
fun(root.left,low,high);
fun(root.right,low,high);
}
}
}
``````

THE END