给定一个二叉树,我想找出其中最大的子树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;
1 回答
请记住,此算法正在向下遍历树 . 访问节点的左子树后,满足以下条件之一:
左子树不是BST =>当前树不是BST
左子树是BST =>当前树中的最小值是
min
左子树没有节点=>当前树中的最小值是当前节点的值
类似地,在遍历右子树之后,当前树中的最大值是当前节点的值或右子树中的最大值(
max
)因此,
int currMin = (leftNodes == 0) ? p->data : min;
行测试条件2或3是否为真,并相应地更新min
的值,以便该值对于测试树中当前节点上方的节点是正确的 .