实现时间复杂度 O(n) - 搜索预序二叉树 C++

Question

二叉搜索树 LCA 让函数 BinarySearchTreeLCA(strArr) 获取存储在 strArr 中的字符串数组，它将包含 3 个元素：第一个元素将是一个二叉搜索树，其中所有唯一值都在前序遍历数组中，第二个和第三个元素将是两个不同的元素值，您的目标是找到这两个值的最低共同祖先。例如：如果 strArr 是 [[[10, 5, 1, 7, 40, 50]", "1", "7"] 那么这棵树如下所示：

        10
       /  \
      5    40
     / \    \
    1   7    50

对于上面的输入，您的程序应该 return 5 因为这是节点的值，它是值为 1 和 7 的两个节点的 LCA。您可以假设您正在搜索的两个节点for in the tree 将存在于树中的某处。

当我为这个挑战提交我的代码时，网站计算我的时间复杂度为 O(n^2)，而最有效的是 O(n)。我认为问题出在“构建树”函数中，因为 for 循环调用了一个递归的“构建树”。请帮我确定是什么导致我的时间复杂度是二次的，以及实现线性时间复杂度的概念

    #include <iostream>
    #include <string>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    using namespace std;

    struct Node {
        int value;
        Node *parent = nullptr;
        Node *leftChild = nullptr;
        Node *rightChild = nullptr;
    };

    Node* findClosestParentOf(Node* n1, Node* n2) {
        vector<int> ancestVals;
        for (n1 = n1; n1 != nullptr; n1 = n1->parent) {
            ancestVals.push_back(n1->value);
        }

        for (n2 = n2; n2 != nullptr; n2 = n2->parent) {
            if (find(ancestVals.begin(), ancestVals.end(), n2->value) != ancestVals.end()) return n2;
        }
        return nullptr;
    }

    Node* searchNodeOf(Node* tree, int val) {
        if(tree->value == val) {
            return tree;
        }
        else {
            if (val < tree->value) return searchNodeOf(tree->leftChild, val);
            else return (searchNodeOf(tree->rightChild, val));
        }
        return nullptr;
    }

    Node* createNode (Node *_parent, int _value) {
        Node *node = new Node;
        node->parent = _parent;
        node->value = _value;

        return node;
    }

    Node* buildTree(Node *&parent, int val) {
        if (val < parent->value) {
            if (parent->leftChild == nullptr) parent->leftChild = createNode(parent, val);
            else buildTree(parent->leftChild, val);
        }
        else {
            if (parent->rightChild == nullptr) parent->rightChild = createNode(parent, val);
            else buildTree(parent->rightChild, val);
        }

        return parent;
    }

    Node* buildTree(vector<int> values) {   
        Node *base = createNode(nullptr, values[0]); 

        for (int i = 1; i < values.size(); i++) {
            buildTree(base, values[i]);
        }
        return base;
    }

    vector<int> stringToInt(string str) {
        vector<int> vec;
        for (char* pch = strtok((char*)str.c_str(), "[ ,]"); pch != NULL; pch = strtok(NULL, "[ ,]")) {
            vec.push_back(stoi(pch));
        }

        return vec;
    }

    int BinarySearchTreeLCA(string strArr[], int length) { 
        vector<int> values = stringToInt(strArr[0]); //O(n)
        Node *tree = buildTree(values); //O(n^2)

        Node* n1 = searchNodeOf(tree, stoi(strArr[1])); //O(n)
        Node* n2 = searchNodeOf(tree, stoi(strArr[2])); //O(n)
        return findClosestParentOf(n1, n2)->value; //O(n)
    }

    int main(void) {
        string A[] = {"[3, 2, 1, 12, 4, 5, 13]", "5", "13"};
        int arrLength = sizeof(A) / sizeof(*A);
        cout << BinarySearchTreeLCA(A, arrLength);
        return 0;
    }

Answer 1

你实现的算法确实不是O(n)。 buildTree 函数实际上具有 O(nlogn) 时间复杂度。

为了以线性时间复杂度解决这个挑战，您甚至可以省略一起构建二叉搜索树。

相反，请考虑这些观察结果：

如果一个节点是共同祖先，那么它的值必须位于两个目标值之间。
并非所有介于两个目标值之间的值都是共同祖先。
并非所有共同祖先的值都介于两个目标值之间
实际上只有一个值位于两个目标值之间，也是一个共同的祖先。这就是LCA。
两个目标值之间的所有其他值必然是以该 LCA 节点为根的子树的一部分。
由于节点是按顺序给出的，我们发现位于两个目标值之间的第一个值必须是LCA（对于以上所有原因）

最后一点描述了你可以实现的线性算法，它也比你做的简单很多。

Answer 2

代码的第 2 次迭代仅搜索识别共同祖先的树并返回最终祖先。根据网站的时间复杂度计算器，删除构建二叉树和比较 2 个向量（祖先路径）的实现将时间复杂度从 O(n^2) 提高到 O(nlogn)。

    #include <iostream>
    #include <string>
    #include <cstring>
    #include <vector>
    using namespace std;


    int maxCalc(int a, int b) {return (a > b) ? a : b;}
    int minCalc(int a, int b) {return (a < b) ? a : b;}

    bool islastAncestor(int node, int max, int min) {return (min < node && max < node || min > node && max > node) ? false : true;}

    vector<int> stringToInt(string str) {
        vector<int> vec;
        for (char* pch = strtok((char*)str.c_str(), "[ ,]"); pch != NULL; pch = strtok(NULL, "[ ,]")) {
            vec.push_back(stoi(pch));
        }
        return vec;
    }

    int BinarySearchTreeLCA(string strArr[], int length) { 
        vector<int> tree = stringToInt(strArr[0]);
        int base = tree.front();
        int max = maxCalc(stoi(strArr[1]), stoi(strArr[2]));
        int min = minCalc(stoi(strArr[1]), stoi(strArr[2]));

        for(int i = 1; i < tree.size(); i++) {
            if (max > base && min > base) {
                if (tree[i] > base && islastAncestor(tree[i], max, min)) return tree[i];
            }
            else if (max < base && min < base && tree[i] < base) {
                if (tree[i] < base && islastAncestor(tree[i], max, min)) return tree[i];
            }
            else return base;
        }
        return 0;
    }

    int main(void) {
        string A[] = {"[3, 2, 1, 12, 4, 5, 13]", "5", "4"};
        int arrLength = sizeof(A) / sizeof(*A);
        cout << BinarySearchTreeLCA(A, arrLength);
        return 0;
    }

实现时间复杂度 O(n) - 搜索预序二叉树 C++

Achieving Time Complexity O(n) - Searching Preorder Binary Tree C++

c++

recursion

binary-tree

time-complexity