32.3 按之字形顺序打印二叉树
上一题的扩展，使用辅助的队列 和栈来实现，注意一下注释里面顺序的坑
public static void printtree(TreeNode root) {
LinkedList<TreeNode> que = new LinkedList<TreeNode>();
Stack<TreeNode> sta = new Stack<TreeNode>();
boolean reverse = true;
int count = 0;// 记录当前层已经打印的个数
int last = 0;// 记录当前层一个有多少个
int layer = 1;// 当前打印层级
TreeNode temp = null;
que.offer(root);
while (!que.isEmpty()|| !sta.isEmpty()) {
if (layer % 2 == 1) {
last = que.size();
count = 0;
while (count < last) {
//System.out.print("lay:"+layer+" value:"+que.peek().val);
System.out.print(que.peek().val);
temp = que.poll();
if (temp.left != null)
sta.add(temp.left);
if (temp.right != null)
sta.add(temp.right);
count++;
}
} else {
last = sta.size();
count = 0;
while (count < last) {
//System.out.print("lay:"+layer+" value:"+sta.peek().val);
System.out.print(sta.peek().val);
temp = sta.pop();
//注意偶数行先存右边，再存左边，试试为啥
if (temp.right != null)
que.add(temp.right);
if (temp.left != null)
que.add(temp.left);
count++;
}
}
layer++;
System.out.println();
}
}
- 二叉搜索树的后序遍历序列
题解对于后序遍历的举例是错误的
image.png
以数组｛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);
}
