有人可以解释一下为什么这个解决方案不起作用吗？

Question

问题：

您已获得一棵包含“N”个节点的二叉树，其中节点具有整数值。你的任务是返回二叉树的最大子树的大小，这也是一个 BST。

二叉搜索树（BST）是一种二叉树数据结构，具有以下属性。

• 节点的左子树仅包含数据小于该节点数据的节点。 • 节点的右子树仅包含数据大于该节点数据的节点。 • 左右子树也必须是二叉搜索树。

*我的解决方案：*

/*
    Following is Binary Tree Node structure:
    class TreeNode
    {
    public:
        int data;
        TreeNode *left, *right;
        TreeNode() : data(0), left(NULL), right(NULL) {}
        TreeNode(int x) : data(x), left(NULL), right(NULL) {}
        TreeNode(int x, TreeNode *left, TreeNode *right) : data(x), left(left), right(right) {}
    };
*/

int ans = 0;

pair<int, bool> Helper(TreeNode* node, int lb, int ub){

   if (!node){return {0, true};}

   if (!node->left && !node->right){ans = max(ans, 1); return {1, true};}

    pair<int, bool> left = Helper(node->left, lb, node->data);
    pair<int, bool> right = Helper(node->right, node->data, ub);

    pair<int, bool> res = {1, false};


    if (left.second && right.second){
        ans = max(ans, res.first + left.first + right.first);
        if (node->data <= lb || node->data >= ub){
            return {0, false};
        }
        res.first += left.first + right.first;
        res.second = true;
        return res;
    }

    return {0, false};

}


int largestBST(TreeNode * root){
    Helper(root, INT_MIN, INT_MAX);
    return ans;
}

*一个可行的解决方案：*

/*
    Time Complexity: O(N)
    Space Complexity: O(N)
    
    where 'N' is the total number of nodes in the binary tree.
*/

struct info 
{
    bool isValid;
    int size, min, max;
};

info maxSize(TreeNode* currNode, int &maxBST)
{
    if (currNode == NULL)
    {
        // isValid, size, min, max.
        return {true, 0, INT_MAX, INT_MIN};
    }


    // Information of left and right subtrees.
    info left = maxSize(currNode -> left, maxBST);
    info right = maxSize(currNode -> right, maxBST);


    info currInfo;

    // Size of current subtree.
    currInfo.size = left.size + right.size + 1;
    
    // Left and Right subtrees must be BST.
    currInfo.isValid = left.isValid & right.isValid;
    
    // Current subtree must form a BST.
    currInfo.isValid &= (currNode -> data > left.max);
    currInfo.isValid &= (currNode -> data < right.min);
    
    // Updating min and max for current subtree.
    currInfo.min = min(min(left.min, right.min), currNode -> data);
    currInfo.max = max(max(left.max, right.max), currNode -> data);


    if (currInfo.isValid == true)
    {
        maxBST = max(maxBST, currInfo.size);
    }

    return currInfo;
}


int largestBST(TreeNode* root)
{
    int maxBST = 0;

    maxSize(root, maxBST);

    return maxBST;
}

因此，在每个节点上，我都会检查 left 是否是 BST，right 是否是 BST，如果是，我只需更新 ans if possble，如果该节点相对于其父节点也是 bst，则返回 true，否则返回 false。

但我不知道为什么它不起作用。请帮忙。

Answer 1

几个问题：

• 您的代码在不确定当前节点是否是 BST 的根的时刻对

  ans

  进行了更新。这是您只能在下一个语句中检查的内容。您应该仅在 BST 验证通过后更新

  ans

  。

  更正：

  if (left.second && right.second){
      // First do the BST check...
      if (node->data <= lb || node->data >= ub){
          return {0, false};
      }
      res.first += left.first + right.first;
      res.second = true;
      // Only when it is BST, update ans:
      ans = max(ans, res.first);
      return res;
  }
  
  
  

• ans

  永远不会重置为 0。它仅设置为 0 一次。因此，如果您的

  largestBST

  函数被第二次调用，它可能会返回错误的答案。

  更正：

  int largestBST(TreeNode * root){
      ans = 0; // Reset at every run
      Helper(root, INT_MIN, INT_MAX);
      return ans;
  }
  

  最好避免使用全局变量。