提高这个二叉树算法的复杂度

Question

我需要找出是否所有可以结束的二叉树路径（这意味着从根开始到只有一个子节点或 none 的节点的所有路径）的长度是否不同不超过一个。

我的工作解决方案是这样工作的：函数 longestPath 找到最长的路径，函数 checkLengths 遍历所有节点以跟踪路径的长度，并且每次只有一个子节点或 none 的节点是发现它检查当前路径的长度和最长路径的长度之间的差异是否大于1。

这个解决方案的复杂度为 O(2n)，因为在最坏的情况下每个节点都必须访问两次，一次用于 longestPath 函数，一次用于 lengthCheck 函数。我想改进 O(n) 的解决方案，但我很难弄清楚如何去做。

编辑：我的解决方案仍然是 O(n)，但我想优化它以通过仅访问每个节点一次而不是两次来找到解决方案。

int lengthCheckFlag=1;
int maxLength=-1;

void longestPath(Node n,int currentLength){
    if(n==nullptr){
        return;
    }
    if(n->left==nullptr && n->right==nullptr){
        if(maxLength==-1){
        maxLength=currentLength;
        }
        else{
            if(currentLength>maxLength){
                maxLength=currentLength;
            }
        }
    }
    longestPath(n->left,currentLength+1);
    longestPath(n->right,currentLength+1);
}

void checkLengths(Node n,int currentLength){
    if(n==nullptr){
        return;
    }
    if(n->left==nullptr || n->right==nullptr){
        if(abs(maxLength-currentLength)>1){
        lengthCheckFlag=0;
        }
    }
    checkLengths(n->left,currentLength+1);
    checkLengths(n->right,currentLength+1);
}

bool lengthCheckWrapper(Node n){
    if(n==nullptr){
        return true;
    }
    longestPath(n,0);
    checkLengths(n,0);
    return lengthCheckFlag;
}

代码更新：

int maxP=-1;
int minP=-1;

void minmaxPaths(Node n,int currentLength){
    if(n==nullptr){
        return;
    }
    if(n->left==nullptr && n->right==nullptr){
        if(maxP==-1){
          maxP=currentLength;
          minP=currentLength;
        }
        else{
            if(currentLength>maxP){
                maxP=currentLength;
            }
            if(currentLength<minP){
                minP=currentLength;
            }
        }
    }
    minmaxPaths(n->left,currentLength+1);
    minmaxPaths(n->right,currentLength+1);
}

bool lengthCheckWrapper(Node n){
    if(n==nullptr){
        return true;
    }
    minmaxPaths(n,0);
    if(abs(minP-maxP)<=1){
       return true;
    }
    return false;
}

Answer 1

一些备注：

O(2n) 等同于 O(n)
您的函数使用不同的条件来识别路径的潜在终点：一个使用 && 运算符（错误），另一个使用 || 运算符（正确）

替代算法的一个想法是进行广度优先遍历。这很有趣，因为约束实际上意味着所有非完美节点（即最多有一个子节点）必须出现在树的底部两层。

因此，如果我们在第一个级别之后找到 2 个以上的级别，我们找到了一个非完美节点，那么我们就违反了并可以停止遍历。

缺点是它占用更多内存。

实现方法如下：

int minmaxDepth(Node root) {
    if (root == nullptr) {
        return 1; // OK
    }
    std::vector<Node> level, nextLevel;
    level.push_back(root);
    int minDepth = INT_MAX;
    int currDepth = 0;
    while (level.size()) {
        currDepth++;
        nextLevel = {};
        for (auto & parent : level) {
            if (currDepth < minDepth  && 
                    (parent->left == nullptr || parent->right == nullptr)) {
                minDepth = currDepth; // Found a path with minimal length
            }
            if (parent->left != nullptr) {
                nextLevel.push_back(parent->left);
            }
            if (parent->right != nullptr) {
                nextLevel.push_back(parent->right);
            }
            if (nextLevel.size() && currDepth > minDepth) {
                return 0; // Paths have lengths that differ more than 1
            }
        }
        level = nextLevel;
    }
    return 1; // All nodes were visited: no violation found
}

Answer 2

无需预先计算最长路径。计算所有路径长度并即时计算，

存储第一个长度，
如果其他长度相差超过 1，您就完成了；
else存储不同的长度，如果任何其他长度与两个存储的长度不同，你就完成了。

提高这个二叉树算法的复杂度

Improving this binary tree algorithm complexity

algorithm

binary-tree

tree-traversal