最大的子樹哪個是二叉搜索樹（BST）

Question

給定一個二叉樹，我想找出它最大的子樹，它是一個 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; 

Answer 1

記住，這個算法遍歷樹自下而上同樣的問題。訪問節點的左子樹後，有下列情況之一爲真：

1. 左子樹不BST =>當前樹是不是BST
2. 左子樹是在當前樹BST =>最小值min
3. 左子樹沒有節點=>在當前樹的最低值是當前節點的值

類似地，穿過右子樹後，在當前樹的最大值是當前節點的任一值或右子樹中的最大值（max）

所以線 int currMin = (leftNodes == 0) ? p->data : min; 測試是否條件2或3是真實的，並且相應地更新的min的值，以使值是用於測試在樹中的當前節點上方的節點正確。