【二叉树】对折纸，从上往下返回折痕的方向

目录

题目

思路

代码实现

注意点

题目

给一张纸，从纸的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。

给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up".

思路

先找规律

对折一次：折痕为“下”；

对折两次：自上向下折痕为“下”、“下”、“上”

...

每折一次，就以上一层二叉树节点为父节点，使其左右节点分别为“上”、“下”，从上到下对折折痕的顺序即为该二叉树按“右子树-父节点-左子树”的顺序遍历，并把对应的值输出的结果。

也可以看做对

正常中序遍历。

用二叉树的遍历思想去解出这道题。

代码实现

class FoldPaper {
public:void traverse(vector&s,string val ,int deep,int n){//deep指的是当前折了多少层if(deep == n)return ;traverse(s,"down",deep+1,n);//右子树s.push_back(val);traverse(s,"up",deep+1,n);//左子树}vector foldPaper(int n) {// write code herevector s;traverse(s,"down",0,n);return s;}
};

注意点

c++ 中字符串用"",字符类型用‘’，单引号中只能有一个字符。'a'表示是一个字符,"a"表示一个字符串相当于'a'+'\0';

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！