最大的子树哪个是二叉搜索树（BST）

给定一个二叉树，我想找出它最大的子树，它是一个 BST。最大的子树哪个是二叉搜索树（BST）

这个问题是Finding the largest subtree in a BST的副本，其中1337c0d3r通过遍历树底向上给出了一个O（n）解。有两行代码混淆了我。任何人都可以帮我解释一下吗？

// Find the largest BST subtree in a binary tree. 
// If the subtree is a BST, return total number of nodes. 
// If the subtree is not a BST, -1 is returned. 
int findLargestBSTSubtree(BinaryTree *p, int &min, int &max, 
        int &maxNodes, BinaryTree *& largestBST) { 
    if (!p) return 0; 
    bool isBST = true; 
    int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, largestBST); 
    int currMin = (leftNodes == 0) ? p->data : min; 
    if (leftNodes == -1 || 
    (leftNodes != 0 && p->data <= max)) 
    isBST = false; 
    int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, largestBST); 
    int currMax = (rightNodes == 0) ? p->data : max; 
    if (rightNodes == -1 || 
    (rightNodes != 0 && p->data >= min)) 
    isBST = false; 
    if (isBST) { 
    min = currMin; 
    max = currMax; 
    int totalNodes = leftNodes + rightNodes + 1; 
    if (totalNodes > maxNodes) { 
     maxNodes = totalNodes; 
     largestBST = p; 
    } 
    return totalNodes; 
    } else { 
    return -1; // This subtree is not a BST 
    } 
} 

BinaryTree* findLargestBSTSubtree(BinaryTree *root) { 
    BinaryTree *largestBST = NULL; 
    int min, max; 
    int maxNodes = INT_MIN; // INT_MIN is defined in <climits> 
    findLargestBSTSubtree(root, min, max, maxNodes, largestBST); 
    return largestBST; 
}

我对以下两行代码感到困惑。根据我的常识，递归遍历左树之后，应该更新max变量，为什么在递归遍历左树之后放置int currMin = (leftNodes == 0) ? p->data : min;？
为int currMax = (rightNodes == 0) ? p->data : max;

... 
int currMin = (leftNodes == 0) ? p->data : min; 
... 
int currMax = (rightNodes == 0) ? p->data : max;

来源

2013-01-24 Fihop

您需要的算法非常接近alpha-beta搜索。（除了你需要访问*几乎*整棵树，不能修剪） – wildplasser

记住，这个算法遍历树自下而上同样的问题。访问节点的左子树后，有下列情况之一为真：

左子树不BST =>当前树是不是BST
左子树是在当前树BST =>最小值min
左子树没有节点=>在当前树的最低值是当前节点的值

类似地，穿过右子树后，在当前树的最大值是当前节点的任一值或右子树中的最大值（max）

所以线 int currMin = (leftNodes == 0) ? p->data : min; 测试是否条件2或3是真实的，并且相应地更新的min的值，以使值是用于测试在树中的当前节点上方的节点正确。

来源

2013-01-25 01:11:07

最大的子树哪个是二叉搜索树（BST）

回答

相关问题