在 BST 中寻找最大的子树 [英] Finding the largest subtree in a BST

问题描述

给定一棵二叉树，我想找出最大的子树，它是其中的 BST.

幼稚的方法:

我有一个简单的方法，我访问树的每个节点并将这个节点传递给 isBST 函数.如果它是 BST，我还将跟踪子树中的节点数.

还有比这更好的方法吗?

解决方案

我已经在我的博客中发布了完整的解决方案和解释:

http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

这个想法是进行深度优先遍历并传递最小值和最大值自下而上而不是自上而下.换句话说，在验证上述节点是否满足 BST 要求之前，我们先验证更深的节点.

这样做的主要原因是当其中一个节点不满足 BST 属性时，上面的所有子树(也包括该节点)也必须不满足 BST 要求.>

与自顶向下的方法相比，自底向上的方法是一个很棒的选择，因为节点总数的结果可以向上传递.这使我们免于一遍又一遍地重新计算.子树的节点总数就是其左右子树的节点总数加一.

该算法在 O(N) 时间复杂度和 O(1) 空间中运行，这是尽可能高效的.(其中 N 是二叉树中节点的总数).

以下是有效的 C++ 代码.实现的棘手部分是处理最小值和最大值如何自底向上传递.请注意，我没有初始化最小值和最大值，因为它们是在树的底部初始化的.

//在二叉树中找到最大的 BST 子树.//如果子树是 BST，则返回节点总数.//如果子树不是 BST，则返回 -1.int findLargestBSTSubtree(BinaryTree *p, int &min, int &max,int &maxNodes, BinaryTree *&最大BST) {如果 (!p) 返回 0；bool isBST = true;int leftNodes = findLargestBSTSubtree(p->left, min, max, maxNodes, maximumBST);int currMin = (leftNodes == 0) ?p-＞数据:分钟；if (leftNodes == -1 ||(leftNodes != 0 && p->data <= max))isBST = 假；int rightNodes = findLargestBSTSubtree(p->right, min, max, maxNodes, maximumBST);int currMax = (rightNodes == 0) ?p->数据:最大值；if (rightNodes == -1 ||(rightNodes != 0 && p->data >= min))isBST = 假；如果(isBST){min = currMin;最大 = currMax;int totalNodes = leftNodes + rightNodes + 1;如果(总节点数 > 最大节点数){maxNodes = totalNodes;最大BST = p;}返回总节点数；} 别的 {返回-1；//这个子树不是 BST}}BinaryTree* findLargestBSTSubtree(BinaryTree *root) {二叉树 *largestBST = NULL;整数最小值，最大值；int maxNodes = INT_MIN;//INT_MIN 定义在<climits>findLargestBSTSubtree(root, min, max, maxNodes, maximumBST);返回最大的BST；}

Given a binary tree, I want to find out the largest subtree which is a BST in it.

Naive approach:

I have a naive approach in mind where I visit every node of the tree and pass this node to a isBST function. I will also keep track of the number of nodes in a sub-tree if it is a BST.

Is there a better approach than this ?

解决方案

I have posted the full solution and explanation in my blog:

http://www.leetcode.com/2010/11/largest-binary-search-tree-bst-in.html

The idea is to do a depth-first traversal and pass min and max values bottom-up instead of top-down. In other words, we verify the deeper nodes before we verify if the above nodes satisfy the BST requirements.

The main reason of doing this is when one of the nodes does not satisfy the BST properties, all subtrees above (which includes this node as well) must also not satisfy the BST requirements.

As compared to the top-down approach, the bottom-up approach is such an awesome choice because the results for total number of nodes could be passed up the tree. This saves us from recalculating over and over again. The total number of nodes for a subtree is simply the total number of nodes of its left and right subtrees plus one.

This algorithm runs in O(N) time complexity and O(1) space, which is as efficient as it can be. (where N is the total number of nodes in the binary tree).

Below is the C++ code that works. The tricky part of the implementation is taking care of how min and max values are passed bottom-up. Please note that I did not initialize min and max values as they are initialized in the bottom of the tree.

// 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;
}

这篇关于在 BST 中寻找最大的子树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！