- 二叉搜索树的后序遍历序列
以数组｛5，7，6，9，11，10，8｝为例，后序遍历结果的最后一个数字8就是根节点的值。在这个数组中，前3个数字5，7和6都比8小，是值为8的结点的左子树结点；后3个数字9，11和10都比8 大，是值为8的结点的右子树结点
于是呢，如果只有两个或者1个数，定义为是真的。具体实现上，先找左边第一个比跟节点（也就是最后一个点）大的值，如果此后的点还存在比根节点小的值，那么就是假的喽，继续递归实现。
public static boolean VerifySquenceOfBST(int[] arr) {
if(arr==null || arr.length==0) return false;
return verify(arr,0,arr.length-1);
}
public static boolean verify(int[] arr,int start,int end) {
if(end-start<=1) return true;
int cur = start;
//找到比跟节点大的地方
while(arr[cur]<arr[end] && cur<end) {
cur++;
}
//后面的节点一旦比根节点还小，就说明不是右子树
for(int i = cur+1;i<end;i++) {
if(arr[i]<arr[end]) return false;
}
return verify(arr, start, cur - 1) && verify(arr, cur, end - 1);
}
- 二叉树中和为某一值的路径
递归的实现，栈弹入弹出的时机选择还蛮妙，测试数据时候猜测+试验出来，理解了一下结果
//二叉树中和为某一值的路径
public static void findpath(TreeNode root, int target) {
if (root == null)
return;
Stack<Integer> path = new Stack<Integer>();
findpathcore(root, target, path);
}
public static void findpathcore(TreeNode root, int target, Stack<Integer> path) {
if (root == null)
return;
//注意push即pop的位置，要在判断外边，这样弹出时候能弹出到最外层，蛮抽象，再看时候可能会更理解……
path.push(root.val);
if (root.left == null && root.right == null) {
if (target == root.val) {
//path.push(root.val);
for (int i : path) {
System.out.print(i + " ");
}
System.out.println(" ");
}
} else {
//path.push(root.val);
findpathcore(root.left, target - root.val, path);
findpathcore(root.right, target - root.val, path);
//path.pop();
}
path.pop();
}
