3

バイナリ ツリーが与えられた場合、その中の BST である最大のサブツリーを見つけたいと思います。

この質問はFinding the maximum subtree in a BST の複製であり、1337c0d3r はツリーを下から上にトラバースすることで O(n) ソリューションを提供します。私を混乱させる2行のコードがあります。誰でも説明できますか？

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

次の2行のコードで混乱しました。私の常識によれば、左ツリーを再帰的にトラバースした後、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;
4

1 に答える 1

3

このアルゴリズムはツリーを下から上にトラバースしていることを思い出してください。ノードの左側のサブツリーにアクセスした後、次のいずれかが true になります。

  1. 左のサブツリーは BST ではありません => 現在のツリーは BST ではありません
  2. 左のサブツリーは BST => 現在のツリーの最小値はmin
  3. 左のサブツリーにはノードがありません => 現在のツリーの最小値は現在のノードの値です

同様に、右側のサブツリーをトラバースした後、現在のツリーの最大値は、現在のノードの値または右側のサブツリーの最大値のいずれかになります ( max)

そのため、この行 int currMin = (leftNodes == 0) ? p->data : min; は条件 2 または 3 が true かどうかをテストし、それにmin応じて の値を更新して、ツリー内の現在のノードより上のノードをテストするための正しい値になるようにします。

于 2013-01-25T01:11:07.447 に答える