为什么相似解的运行时间相差这么大?
Why the run time of similar solution is so different?
还有一个problem in LeetCode. I use a straightforward recursive solution to solve it, but the run time is to long, which is 170ms. Then I found a similar solution,也是递归的,这个运行的时间也就10ms左右。为什么?
我的解决方案:
class Solution
{
public:
bool isBalanced(TreeNode* root)
{
if (root == nullptr)
return true;
bool left = isBalanced(root->left);
bool right = isBalanced(root->right);
bool curr = false;
int sub = height(root->left) - height(root->right);
if (sub < 2 && sub > -2)
curr = true;
return left && right && curr;
}
private:
int height(TreeNode* root)
{
if (root == nullptr)
return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
};
我找到的快速解决方案:
class Solution {
public:
bool isBalanced(TreeNode *root) {
if (root==NULL) return true;
int left = treeDepth(root->left);
int right = treeDepth(root->right);
if (left-right>1 || left-right < -1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
int treeDepth(TreeNode *root) {
if (root==NULL){
return 0;
}
int left=1, right=1;
left += treeDepth(root->left);
right += treeDepth(root->right);
return left>right?left:right;
}
};
谢谢!
您的解决方案同时调用 isBalanced
和 height
,总是。对于树中的每个节点。
更快的解决方案为每个节点调用 treeDepth
,但提前退出并且如果知道树不平衡则不会调用 isBalanced
。不调用不必要的 (recursive/expensive) 函数是一种优化。
还有一个problem in LeetCode. I use a straightforward recursive solution to solve it, but the run time is to long, which is 170ms. Then I found a similar solution,也是递归的,这个运行的时间也就10ms左右。为什么?
我的解决方案:
class Solution
{
public:
bool isBalanced(TreeNode* root)
{
if (root == nullptr)
return true;
bool left = isBalanced(root->left);
bool right = isBalanced(root->right);
bool curr = false;
int sub = height(root->left) - height(root->right);
if (sub < 2 && sub > -2)
curr = true;
return left && right && curr;
}
private:
int height(TreeNode* root)
{
if (root == nullptr)
return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
}
};
我找到的快速解决方案:
class Solution {
public:
bool isBalanced(TreeNode *root) {
if (root==NULL) return true;
int left = treeDepth(root->left);
int right = treeDepth(root->right);
if (left-right>1 || left-right < -1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
int treeDepth(TreeNode *root) {
if (root==NULL){
return 0;
}
int left=1, right=1;
left += treeDepth(root->left);
right += treeDepth(root->right);
return left>right?left:right;
}
};
谢谢!
您的解决方案同时调用 isBalanced
和 height
,总是。对于树中的每个节点。
更快的解决方案为每个节点调用 treeDepth
,但提前退出并且如果知道树不平衡则不会调用 isBalanced
。不调用不必要的 (recursive/expensive) 函数是一种优化。