搜索二叉树的特点：
如果根有左孩子，那么左子树所有节点的值都小于根
如果根有右孩子，那么右子树所有节点的值都大于等于根
后序遍历的顺序是 左右根
我们根据数组中最后一个数作为根节点，往前找直到第一个比根小的数字，依次划分左右子树。并确保左子树没有比根大的节点
public boolean sequenceOfBST(int [] sequence){
if(sequence.length == 0) return false;
if(sequence,length == 1) return true;
return judge(int [] sequence, 0, int sequence.length - 1);
public boolean judge(int [] sequence, int start, int root){
if(start >= root) return true;
int i = start;
while(i < root && sequence[i] < sequence[root])
i++;
for(int j = i; j < root; j++){
if(sequence[j] < sequence[root])
return false;
}
return (judge(int [] sequence, start, i-1) && (judge(int [] sequence, i, root - 1);
}
#其他方法有，
从数组的最后一个值开始往前，把每一个值都当作根节点遍历一遍数组，
设置left和right指针，right从后往前，把每个值都当作根节点，每一次left都从0开始往后，
left应该先经过左子树，所以前面的值都比right指向的值小；后经过右子树，所以后面的值都比right指向的值大。
最后left与right指针重合，right指针往前一步，left从0开始，新的一轮遍历
最后，right为0，说明数组是搜索树的后序遍历。
复杂度为O(n^2)
public boolean verify_Iteratively(int [] sequence){
int left = 0;
int right = sequence.length - 1;
while(left < right && right != 0){
while(sequence[left] < sequence[right]) //循环结束时，left位于右子树上最左的节点。即第一个大于根的节点
left++;
while(sequence[left] > sequence[right] // 循环结束时，left指向root
left++;
if(left<right) return false; //如果left没有到达根节点，说明不满足左子树所有节点均小于根，右子树所有节点均大于根
left = 0;
right--;
}
return (right == 0) ? true:false;
}
最后一个为根节点
从根节点的前一个节点开始，往前遍历，第一个比根节点大的节点是右子树。记为right
从根节点的前一节点开始，往前遍历，第一个比根节点小的节点是左子树。记为left
判断（left，right）中的值是否都比根节点大。存在小于根节点，返回false
判断（0，left）中的值是否都比根节点小，存在大于根节点，返回false
返回true
时间复杂度O(n)
就是非递归版本
public boolean judge(int [] sequence){
if(sequence == null) return true;
int len = sequence.length - 1;
int left = -1;
int right = -1;
for(int i = len - 1; i >= 0; i--){
if(right == -1&& sequence[i] > sequence[len]
right = i;
if(left == -1&& sequence[i] < sequence[len]
left = i;
}
for(int i = right - 1; i > left; i--){
if(sequence[i] < sequence[len])
return false;
}
for(int i = left - 1; i >= 0; i--){
if(sequence[i] > sequence[len])
return false;
}
return true;
}
没有接受检验，不确定逻辑是否没差错
public boolean judge(int [] sequence){
if(sequence == null) return false;
if(sequence.length == 1) return true;
int len = sequence.length - 1;
int left = -1;
int right = -1;
for(int i = len - 1; i >= 0; i--){
if(right == -1&& sequence[i] > sequence[len]
right = i;
if(left == -1&& sequence[i] < sequence[len]
left = i;
}
while(right > left){
for(int root = len; root > left; root--){
for(int i = root - 1; i > left; i--){
if(sequence[i] < sequence[root])
return false;
}
}
for(int root = left; root >0; root--){
for(int i = root - 1; i >=0; i--){
if(sequence[i] > sequence[root])
return false;
}
}
}
return true;
}
##题目 二叉树中和为某一值的路径
输入一颗二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根节点往下一直到叶节点所经过的结点形成一条路径。
#分析
思路比较明了，遍历二叉树。
需要维护两个值，一个是路径信息一个是节点的值。退出这个节点的时候路径和也要相应的减去这个节点的值
思路
用前序遍历的方式访问到某一结点时，把该节点添加到路径上，并将target减去该节点值。
如果该节点刚好为叶节点且target变成0，把整个路径添加到用来记录路径的数组中。
如果当前不是叶节点，则继续往下递归。
当前节点访问结束后递归函数将自动退回它的父节点。因此我们要在函数退出之前在数组中删掉这个节点，保证返回父节点时路径刚好从根节点到父节点。
注意在回退的时候，目标值加回退出的节点的值
public ArrayList<ArrayList<Integer>> numIsPath(TreeNode Node, int target){
ArrayList<ArrayList<Integer>> val = new ArrayList<ArrayList<Integer>>;
ArrayList<Integer> temp = new ArrayList<Integer>;
if(root == null) return val;
target -= root.val;
temp.add(root.val);
if(target == 0 && root.left == null && root.right == null)
val.add(new ArrayList<integer>(temp));
else{
numIsPath(root.left, target);
numIsPath(root.right, target);
}
temp.remove(temp.size() - 1); //此时temp中最后的节点是叶节点的父节点
target += root.val; //此时的root是叶节点，且这条路径的路径和不等于输入整数
return val;
}
原文：https://www.cnblogs.com/cherry-BAIL/p/13069834.html