鑑於二叉樹，找到最大的子樹，這是一個二叉搜索樹

Question

我在採訪中被問及這個問題。我以找到所有子樹並檢查它們是否是bst的幼稚方法開始了我的答案。在這個過程中，我們將記錄迄今爲止看到的max bst的大小。

有沒有比這更好的方法？

Answer 1

這個website似乎涵蓋了這個問題：二進制搜索樹檢查。具體來說，這裏是對C++解決方案的摘錄

/* 
Returns true if the given tree is a binary search tree 
(efficient version). 
*/ 
int isBST2(struct node* node) { 
    return(isBSTUtil(node, INT_MIN, INT_MAX)); 
} 
/* 
Returns true if the given tree is a BST and its 
values are >= min and <= max. 
*/ 
int isBSTUtil(struct node* node, int min, int max) { 
    if (node==NULL) return(true); 

    // false if this node violates the min/max constraint 
    if (node->data<min || node->data>max) return(false); 

    // otherwise check the subtrees recursively, 
    // tightening the min or max constraint 
    return 
    isBSTUtil(node->left, min, node->data) && 
    isBSTUtil(node->right, node->data+1, max) 
); 
} 

Answer 2

我假設有O（n）複雜性來解決。

bool is_bst(node * cur) 
{ 
    if (cur == NULL) 
    return true; 

    // if calculated before cur vertex. 
    if (hash_set_bst[cur] != -1) 
     return hash_set_bst[cur]; 

    int left_value = MIN; 
    int right_value = MAX; 
    if (cur -> left != NULL) 
     left_value = cur -> left -> value; 
    if (cur -> right != NULL) 
     right_value = cur -> right -> value; 

    if (cur -> value > left_value && cur -> value < right_value) 
    { 
     hash_set_bst[cur] = is_bst(cur->left) && is_bst(cur->right); 
     return hash_set_bst[cur]; 
    } 
    else 
    { 
     hash_set_bst[cur] = 0; 
     is_bst(cur->left); 
     is_bst(cur->right); 
     return hash_set_bst[cur]; 
    } 
} 

現在對於每個節點，你知道它是否可以啓動BST或不。現在，您需要計算子樹大小，然後遍歷所有節點，並確定節點是否可以啓動BST時標記的最大大小是多少。

要計算尺寸，你可以做到以下幾點：

int dfs(node * cur) 
{ 
    if (cur == NULL) return 0; 
    size[cur] = 1 + dfs(cur->left) + dfs(cur->right); 
    return size[cur]; 
} 

Answer 3

我認爲您的解決方案是這樣的：

for each subtree of the tree: 
    if the subtree is a binary search tree: 
     compute its size 
     if it is the largest one found so far: 
      best = subtree 
return best 

這是低效的，因爲它確實Ø每個子樹（n）的工作，並且最多有n棵子樹。

您只需走一遍整棵樹就可以做得更好。

// Walk the subtree at node. Find the largest subtree that is a binary search tree 
// and return that tree in *result. Also return that subtree's size and the range 
// of values it covers in *size, *min, and *max. 
void 
walk(Node *node, Node **result, size_t *size, Value *min, Value *max) 
{ 
    Node *result0 = NULL; 
    size_t size0 = 0; 
    Value min0, max0; 
    if (node->left) 
     walk(node->left, &result0, &size0, &min0, &max0); 

    Node *result1 = NULL; 
    size_t size1 = 0; 
    Value min1, max1; 
    if (node->right) 
     walk(node->right, &result1, &size1, &min1, &max1); 

    // If both subtrees are search trees and node->value falls between them, 
    // then node is a search tree. 
    if (result0 == node->left 
     && result1 == node->right 
     && (node->left == NULL || max0 <= node->value) 
     && (node->right == NULL || node->value <= min1)) 
    { 
     *result = node; 
     *size = size0 + 1 + size1; 
     *min = node->left == NULL ? node->value : min0; 
     *max = node->right == NULL ? node->value : max1; 
    } else if (size0 >= size1) { 
     *result = result0; 
     *size = size0; 
     *min = min0; 
     *max = max0; 
    } else { 
     *result = result1; 
     *size = size1; 
     *min = min1; 
     *max = max1; 
    } 
} 

Node * 
findLargestBinarySearchSubtree(Node *root) 
{ 
    Node *result; 
    size_t size; 
    Value min, max; 
    walk(root, &result, &size, &min, &max); 
    return result; 
} 

Answer 4

在二叉樹的遍歷順序做一個，如果有子樹是BST中序遍歷將產生一個遞增的序列，當您去記錄樹的大小。當你擊中一個斷點時，遞歸遍歷該樹使用斷點作爲根，記錄它的大小。挑選最大的一個。

Answer 5

如果你這樣做：

1. 調整你的圖形
2. 使用克魯斯卡爾算法這樣的重量。

---

a。從你的一組邊中選擇最低輪廓的邊緣。

b。僅當添加該邊緣不會破壞您的bst約束時才創建樹。

c。從您的邊緣設置中移除該邊緣。

您可能會得到幾棵樹（因爲當bst約束不滿足時丟棄邊緣可能會使您斷開原始圖形），因此只需選擇具有更多節點的那個。