题目地址:https://leetcode-cn.com/problems/largest-bst-subtree/

题目描述

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:

  • A subtree must include all of its descendants.

Example:

Input: [10,5,15,1,8,null,7]

   10 
   / \ 
  5  15 
 / \   \ 
1   8   7

Output: 3
Explanation: The Largest BST Subtree in this case is the highlighted one.
             The return value is the subtree's size, which is 3.

Follow up:

  • Can you figure out ways to solve it with O(n) time complexity?

题目大意

找出一个树中最大的BST有多少个节点。

解题方法

DFS

如果用简单的方法做,就是先判断每个树是不是BST,如果是则返回其节点个数,如果不是就递归他的左右子树,最后结果要用最大值。

C++代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int largestBSTSubtree(TreeNode* root) {
        if (!root) return 0;
        int res = 0;
        if (isBST(root, INT_MIN, INT_MAX)) {
            return countNodes(root);
        }
        res = max(res, largestBSTSubtree(root->left));
        res = max(res, largestBSTSubtree(root->right));
        return res;
    }
    bool isBST(TreeNode* root, int minVal, int maxVal) {
        if (!root) return true;
        if (root->val >= maxVal)
            return false;
        if (root->val <= minVal)
            return false;
        return isBST(root->left, minVal, root->val) && isBST(root->right, root->val, maxVal);
    }
    int countNodes(TreeNode* root) {
        if (!root) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
private:
    int res = 0;
};

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

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发