1373. 二叉搜索子树的最大键值和

Powered by:NEFU AB-IN

Link

1373. 二叉搜索子树的最大键值和

• 题意

  给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

• 思路

  判断一颗树是否是二叉搜索树的充分条件:

  • 根节点值大于左子树最大值，说明比左子树所有元素都大
  • 根节点值小于右子树最小值，说明比右子树所有元素都小
  • 左子树是二叉搜索树
  • 右子树是二叉搜索树

  满足上面四个条件，我们就推断出当前树是一颗二叉搜索树。
  所以我们可以在每层递归里记录四个值:

  • 当前树的最小值
  • 当前树的最大值
  • 当前树的和
  • 当前树是否是二叉搜索树

  当前调用层的每个值都可以根据它的左子树和右子树返回的数组，以及它本身的值来更新。

• 代码

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
      int ans = 0;
      
      
      // 返回值:            {min, max, sum, isBiSearchTree}
      vector<int> dfs(TreeNode* root){
          if(!root) return {INT_MAX, INT_MIN, 0, true}; // 初始化
          // 比如最小值初始化为最大值，这样可以一直满足 val < right[0]这个不等式
          // 将isB也初始化为true，方便判断叶节点的情况
          auto left = dfs(root->left);
          auto right = dfs(root->right);
          
          int val = root->val;
          int sum = left[2] + right[2] + val;
          bool isB = false;
          
          // 判断是否为二叉搜索树，四个条件
          if(val > left[1] && val < right[0]){
              if(left[3] && right[3]) isB = true;
          }
          
          // 更新值
          if(isB) ans = max(ans, sum);
          int mx = max({left[1], right[1], val});
          int mn = min({left[0], right[0], val});
          
          return {mn, mx, sum, isB};
      }
      
      
      
      int maxSumBST(TreeNode* root) {
          dfs(root);
          return ans;
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48