PAT 1155 Heap Paths (30 分)- 甲级

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) the key of C. A common implementation of a heap is the binary heap, in which the tree is a complete binary tree. (Quoted from Wikipedia at https://en.wikipedia.org/wiki/Heap_(data_structure))

One thing for sure is that all the keys along any path from the root to a leaf in a max/min heap must be in non-increasing/non-decreasing order.

Your job is to check every path in a given complete binary tree, in order to tell if it is a heap or not.

Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (1<N≤1,000), the number of keys in the tree. Then the next line contains N distinct integer keys (all in the range of int), which gives the level order traversal sequence of a complete binary tree.

Output Specification:
For each given tree, first print all the paths from the root to the leaves. Each path occupies a line, with all the numbers separated by a space, and no extra space at the beginning or the end of the line. The paths must be printed in the following order: for each node in the tree, all the paths in its right subtree must be printed before those in its left subtree.

Finally print in a line Max Heap if it is a max heap, or Min Heap for a min heap, or Not Heap if it is not a heap at all.

Sample Input 1:
8
98 72 86 60 65 12 23 50
Sample Output 1:
98 86 23
98 86 12
98 72 65
98 72 60 50
Max Heap
Sample Input 2:
8
8 38 25 58 52 82 70 60
Sample Output 2:
8 25 70
8 25 82
8 38 52
8 38 58 60
Min Heap
Sample Input 3:
8
10 28 15 12 34 9 8 56
Sample Output 3:
10 15 8
10 15 9
10 28 34
10 28 12 56
Not Heap

题目大意:给出一颗完全二叉树,打印出从根节点到所有叶节点的路径,打印顺序先右后左,即先序遍历的镜像。然后判断该树是大顶堆、小顶堆或者不是堆~

分析:1.深搜打印出所有路径(从右往左,即先序的镜像),vector保存一路上的节点,通过push和pop回溯,维护路径,index <= n是对只有左叶节点没有右叶节点的点特判
2.判断是否为堆:从第二个节点开始遍历,如果比父节点小,就不是小顶堆,如果比父节点大,就不是大顶堆~

 

在二叉树中有两个结点m和n,若m是n的祖先,则使用后序遍历可以找到从m到n的路径

首先需要理解的是,前中后序遍历都是通过递归的方式,将后来需要用到的结点保存在栈中,比如下面这颗树:

如果是前序遍历,根左右,过程是:根节点m入栈并输出,访问m的左孩子a,a入栈并输出,访问a的左孩子c,c入栈并输出,c没有左孩子,无元素入栈,c没有右孩子,无元素入栈,c出栈,此时栈顶元素为a,访问a元素的右孩子d,d入栈并输出,d没有左孩子,无元素入栈,d没有右孩子,无元素入栈,d出栈,a左右子树都访问完了所以出栈,现在栈顶元素是m,m已经没有作用了所以出栈,访问m的右孩子b,m的右孩子b入栈并输出,接着访问b的左孩子e,e入栈并输出……

如果中序遍历,左根右,过程是:根节点m入栈,访问m的左孩子,所以m的左孩子a入栈,访问a的左孩子,所以a的左孩子c入栈,c没有左孩子,c现在输出并出栈,c没有右孩子所以没有元素入栈,现在栈顶元素是a,a输出并出栈,a的右孩子d入栈,此时d没有左孩子所以没有元素入栈,d输出并出栈,d没有右孩子所以没有元素入栈,现在栈顶元素是m,m输出,此时m已经没有作用了所以出栈,m的右孩子b入栈,访问b的左孩子,所以b的左孩子e入栈……

所以在前序和中序的过程中,如果n在m的右子树部分,遍历过程中找到了n,但是m已经不在栈中,因为栈中只会保留等会需要用到的e和b结点,而m已经完成了访问根结点和m的左子树的任务,已经被出栈,所以无法追溯n如何走到m

但是后序遍历就不一样啦,后序的顺序是左右根,所以只要m的左右子树还没遍历完成,m就不能出栈,在遍历m的左右子树过程中,无论在m的左边还是右边找到了n,都可以直接返回然后根据栈中的路径让n找到回到m的路,这样就能找到m到n的路径~

所以一旦n在m的右子树,且离的较远,m就会在前序和中序的过程中因为已经完成了访问左、访问根的任务,而被栈遗忘,让找到了n的时候也不知怎么回到m……而只有后序会让作为祖先(子树的根)的m永远被铭记直到n找到m为止…

【iOS】Tab Bar 的 Item 按钮的像素大小要求

根据苹果官方人机界面指南(Human Interface Guidelines)可以得知:

iOS系统会根据设备和方向显示两种标签栏:常规(Regular)紧凑(Compact),所以在设置自定义Tab Bar Item的时候也应该包含常规和紧凑两种不同的尺寸

根据图形是圆形、方形、宽形、高形,像素也有不同的要求:

如果图标是圆形的,应该提供:25pt@2x、25pt@3x、18pt@2x、18pt@3x

如果图标是方形的,应该提供:23pt@2x、23pt@3x、17pt@2x、17pt@3x

如果图标是宽形的,应该提供:31pt@2x、31pt@3x、23pt@2x、23pt@3x

如果图标是高形的,应该提供:28pt@2x、28pt@3x、20pt@2x、20pt@3x

以下是完整表格~

【iOS】Image图片属性之Render As Template Image

把图片设置成Render as Template Image,系统会忽略图像的颜色信息,并根据图像中的alpha值创建图像模板,图像中alpha值 < 1.0的部分被视为完全透明,alpha值 = 1.0的部分为Image Tint的颜色,默认Default为蓝色

假设原图为:

将其设置为Render as Template Image,并且将Tab Bar Item设置为该图片,则Tab Bar的Item会变为这样:

如果将Tab BarImage Tint设置为红色,则Tab Bar的Item会变为这样: