赞
踩
/* 方法一: 算法思想: 完全递归,通过循环将第i个位置转换为(i-1)*(n-i)个结果的组合 由于每次都从结束点重新递归,因此该方法会超时。 */ typedef struct TreeNode Node; #define LEN 0xfff void rec(int n, Node **ret, int *ret_index){ int i, j, k; Node *node; Node *arr1[LEN], *arr2[LEN]; int cnt1=0, cnt2=0; if(n == 2 || n == 0) { *ret_index = 0; return; } if(n == 1) { node = (Node *)malloc(sizeof(Node)); node->val = 0; node->left = NULL; node->right = NULL; ret[(*ret_index)] = node; (*ret_index)++; return; } *ret_index = 0; for(i=1; i<=n; i++){ rec(i-1, arr1, &cnt1); rec(n-i, arr2, &cnt2); //printf("i-1 = %d, n-i=%d, cnt1 = %d, cnt2 = %d\n", i-1, n-i, cnt1, cnt2); for(j=0; j<cnt1; j++){ for(k=0; k<cnt2; k++){ node = (Node *)malloc(sizeof(Node)); node->val = 0; node->left = arr1[j]; node->right = arr2[k]; ret[*ret_index] = node; (*ret_index)++; } } } } struct TreeNode** allPossibleFBT(int N, int* returnSize){ Node **ret = (Node **)malloc(sizeof(Node *) * LEN); int ret_index = 0; rec(N, ret, &ret_index); *returnSize = ret_index; printf("ret_index = %d\n", ret_index); return ret; } /** 方法二: 也是递归的思想,将求N的转化为求N-1的,将前面已经计算的结果保存到一个数组中。 */ typedef struct TreeNode Node; typedef struct ret_node{ Node **roots; int cnt; } RNode; #define LEN 0xffff void rec(int n, RNode *rnodes){ int i, j, k; Node *node; int len = 0; int index = 0; if(n<0) return; if(n == 0) { rnodes[n].cnt = 0; rnodes[n].roots = NULL; return; } if(n == 1) { node = (Node *)malloc(sizeof(Node)); node->val = 0; node->left = NULL; node->right = NULL; rnodes[1].roots = (Node **)malloc(sizeof(Node *) * 1); rnodes[1].cnt = 1; rnodes[1].roots[0] = node; return; } rec(n-1, rnodes); /* get length of Nth result from 0-N-1 results */ len = 0; for(i=1; i<=n; i++){ for(j=0; j< rnodes[i-1].cnt; j++){ for(k=0; k<rnodes[n-i].cnt; k++){ len += rnodes[i-1].cnt * rnodes[n-i].cnt; } } } rnodes[n].roots = (Node **)malloc(sizeof(Node *)*len); rnodes[n].cnt = 0; for(i=1; i<=n; i++){ for(j=0; j< rnodes[i-1].cnt; j++){ for(k=0; k<rnodes[n-i].cnt; k++){ //printf("i-1 = %d, n-i=%d, cnt1 = %d, cnt2 = %d, len = %d\n", i-1, n-i, rnodes[i-1].cnt, rnodes[n-i].cnt, len); node = (Node *)malloc(sizeof(Node)); node->val = 0; node->left = rnodes[i-1].roots[j]; node->right = rnodes[n-i].roots[k]; rnodes[n].roots[index++] = node; rnodes[n].cnt++; } } } } struct TreeNode** allPossibleFBT(int N, int* returnSize){ int i; RNode r_ret[LEN]; memset(r_ret, 0, sizeof(r_ret)); rec(N, r_ret); *returnSize = r_ret[N].cnt; for(i=0; i<N; i++){ if(r_ret[i].roots){ free(r_ret[i].roots); } } return r_ret[N].roots;; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。