1.有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树。
给定二叉树的根结点root,请返回打印结果,结果按照每一层一个数组进行储存,所有数组的顺序按照层数从上往下,且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
/*struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { }};*/class TreePrinter {public: vector> printTree(TreeNode* root) { vector > as; vector a; TreeNode*last = root; TreeNode*nlast = root; TreeNode* node; queue qu; qu.push(root); while(!qu.empty()){ node = qu.front(); qu.pop(); a.push_back(node->val); if(node->left) {qu.push(node->left); nlast = node->left;} if(node->right) {qu.push(node->right) ;nlast = node->right;} if(last == node){ last = nlast; as.push_back(a); a.clear(); } } return as; // write code here }};
2.如果对于一个字符串A,将A的前面任意一部分挪到后边去形成的字符串称为A的旋转词。比如A="12345",A的旋转词有"12345","23451","34512","45123"和"51234"。对于两个字符串A和B,请判断A和B是否互为旋转词。
给定两个字符串A和B及他们的长度lena,lenb,请返回一个bool值,代表他们是否互为旋转词。
测试样例:
"cdab",4,"abcd",4
返回:true
class Rotation {public: bool chkRotation(string A, int lena, string B, int lenb) { // write code here if(lena!=lenb){ return false; } string C= A+A; for(int i=0;i