二叉搜索樹 LCA 使用函式 BinarySearchTreeLCA(strArr) 獲取存盤在 strArr 中的字串陣列，該陣列將包含 3 個元素：第一個元素將是一個二叉搜索樹，其中所有唯一值都在前序遍歷陣列中，第二個和第三個元素將是兩個不同的值，您的目標是找到這兩個值的最低共同祖先。例如：如果 strArr 是 ["[10, 5, 1, 7, 40, 50]", "1", "7"] 那么這棵樹如下所示：
10
/ \
5 40
/ \ \
1 7 50
對于上面的輸入，您的程式應該回傳 5，因為這是節點的值，即值為 1 和 7 的兩個節點的 LCA。您可以假設您在樹中搜索的兩個節點將存在于樹。
當提交我的這個挑戰的代碼時，網站計算我的時間復雜度為 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;
}
uj5u.com熱心網友回復：
您實作的演算法確實不是 O(n)。該buildTree函式實際上具有 O(nlogn) 時間復雜度。
為了以線性時間復雜度解決這一挑戰，您甚至可以省略構建二叉搜索樹。
相反，請考慮以下觀察結果：
如果一個節點是一個共同的祖先，那么它必須有一個介于兩個目標值之間的值。
并非位于兩個目標值之間的所有值都是共同祖先。
并非所有共同祖先都是兩個目標值之間的值
實際上只有一個值位于兩個目標值之間，它也是一個共同的祖先。這就是 LCA。
介于兩個目標值之間的所有其他值必然是植根于該 LCA 節點的子樹的一部分。
由于節點是預先給定的，我們發現位于兩個目標值之間的第一個值必須是 LCA（出于上述所有原因）
最后一點描述了您可以實作的線性演算法，這也比您所做的要簡單得多。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/439496.html
上一篇：遞回方法即使有條件也不會停止