描述

We use the following method (presented in pseudocode) to do a traversal on a binary tree T. Each node of T has an integer value, and may have no child, one left child, one right child or both left and right children. Each child is also a node of the binary tree.

Algorithm TraversalInput: the root node r of T or a T's sub-tree.Output: The Traversal Sequence of values of nodes.  procedure Travel(node r)    Travel(r.leftChild)    Print(r.value)    Travel(r.rightChild)  end procedure

Note that the algorithm does not check whether a node has left or right child. So it may get wrong during running. Suppose that if we call procedure Travel(r) when node r does not exist, the procedure will simply print a sharp sign ''#'' instead of executing the body of the procedure.

Given a wrong Traversal Sequence containing integers and ''#''s, you should answer whether this sequence can be a possible output when calling Travel(R), where R is the root of a legal binary tree. Note that an empty tree is also a legal binary tree, which means, it is possible that even R does not exist.

输入

The first line contains an integer T (1 ≤ T ≤ 100), indicating the number of test cases.

For each test case:

The first line contains an integer N (1 ≤ N ≤ 1000), indicating the length of the sequence (the total number of integers and ''#''s).

The second line contains N elements, separated by a single space. Each element is either an integer (non-negative and no more than 10^9) or a sharp sign ''#''.

输出

For each test case, output ''Yes'' if this Traversal Sequence can be an output of some input, or ''No'' otherwise. The string should be printed on a single line.

样例输入

23# 1 #42 # # 1

样例输出

YesNo

   

题目描述：对一颗二叉树进行中根遍历，若遍历过程中根结点没有左孩/右孩，则输出#，否则输出编号。

   题目分析：根据中根遍历的性质，遍历做节点的过程唯有出现了某个结点不存在儿子之后才结束，因此第一个输出的必定为#。进一步分析，输出＃后，根据题目意思，必定将会输出编号，然后进行右儿子的递归；而递归也唯有遇到某个结点没有儿子后才停止。因此可以分析出来，第1，3，5.....2n+1(奇数)位必定为#，2，4，6.......2n必定为数字，因此只需稍加判断即可做出答案。

    

#include 
    
     using namespace std;int main(){    int t;    scanf("%d",&t);    while(t--){        int n;        scanf("%d",&n);        bool vis=true;        for(int i=1;i<=n;i++){            string str;            cin>>str;            if(!vis) continue;            if(i&1&&str!="#") vis=false;            else if(i&1==0&&str=="#") vis=false;        }        if(vis) puts("Yes");        else puts("No");    }    return 0;}