递归做二叉树的宽度

来源：百度知道 编辑：UC知道 时间：2024/06/03 07:25:22
我知道用队列非递归求二叉树宽度的算法，请问用递归做二叉树宽度，应该如何实现？ 请各位高手不吝赐教！

def permute(str,prefix):
if len(str) == 0:
print prefix,
return
permute(str[1:],prefix)
permute(str[1:],prefix+str[0])

permute('123','')

这是解答的结果，和上面二叉树来表示完全一致

3 2 23 1 13 12 123

由于用Python的人并不是很多，所以我也用C写了个程序作为参考

#include <iostream>
#include <cstring>

#define BUFFER_SIZE 255

using namespace std;

void permute(char *src, char *prefix)
{
char buf[BUFFER_SIZE];
int len = strlen(prefix);

if (strlen(src) == 0)
{
cout<<prefix<<" ";
return;
}
strcpy(buf,prefix);
permute(src+1, prefix);
prefix[len] = *src;
prefix[len+1] = '\0';
permute(src+1, prefix);
}

int main(int argc,char argv)
{
char buf[BUFFER_SIZE] = "";
pe