返回信息流刚刚做了下108题和109题，108题是把数组转化成平衡遍历二叉树，运行时间是16ms，最短的。109题是把链表转化成平衡二叉树，需要遍历一下链表。但是转化是一样的，但是运行时长是32ms，不是最短的了。108题是通过调用有返回值的递归，后来109题尝试通过传参无返回值递归，运行时长是28ms了，最短了。我以为无返回值得递归更快，把108题也这样改了，但是运行时长反而成了20ms。请问这是什么原因造成的，应该使用哪种方式递归更好？不多说了，代码运行时长如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* convert(vector<int>& nums,int left,int right){
if(left>right){
return NULL;
}
int mid=left+(right-left)/2;
TreeNode* root=new TreeNode(nums[mid]);
root->left=convert(nums,left,mid-1);
root->right=convert(nums,mid+1,right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return convert(nums,0,nums.size()-1);
}
};
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void convert(vector<int>& nums,int left,int right,TreeNode* &root){
if(left>right){
root=NULL;
return;
}
int mid=left+(right-left)/2;
root=new TreeNode(nums[mid]);
convert(nums,left,mid-1,root->left);
convert(nums,mid+1,right,root->right);
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root;
convert(nums,0,nums.size()-1,root);
return root;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* convert(vector<int>& nums,int left,int right){
if(left>right){
return NULL;
}
int mid=left+(right-left)/2;
TreeNode* root=new TreeNode(nums[mid]);
root->left=convert(nums,left,mid-1);
root->right=convert(nums,mid+1,right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
vector<int> nums;
while(head){
nums.push_back(head->val);
head=head->next;
}
return convert(nums,0,nums.size()-1);
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void convert(vector<int>& nums,int left,int right,TreeNode* &root){
if(left>right){
root=NULL;
return;
}
int mid=left+(right-left)/2;
root=new TreeNode(nums[mid]);
convert(nums,left,mid-1,root->left);
convert(nums,mid+1,right,root->right);
//root->left=convert(nums,left,mid-1);
//root->right=convert(nums,mid+1,right);
// return root;
}
TreeNode* sortedListToBST(ListNode* head) {
vector<int> nums;
TreeNode* root;
while(head){
nums.push_back(head->val);
head=head->next;
}
convert(nums,0,nums.size()-1,root);
return root;
//return convert(nums,0,nums.size()-1,root);
}
};
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #87968同步于 2015/9/25
ACM_ICPC机器人发帖
leetcode 108题 109题 运行时间差异
chenhebing
2015/9/25镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。