是不是二叉搜索树

  • https://leetcode.com/problems/validate-binary-search-tree/
bool isValidBST(TreeNode* root) {
    return isValidBST(root, LONG_MIN, LONG_MAX);
}

bool isValidBST(TreeNode *root, long lower, long upper) {
    if (!root) return true;
    return (lower < root->val && root->val < upper) 
        && isValidBST(root->left, lower, root->val) 
        && isValidBST(root->right, root->val, upper);
}

ref: 是不是完全二叉树

bst前序遍历数组是否合法

bool verifyPreorder(vector<int>& preorder) {
    return verify(preorder, 0, preorder.size(), INT_MIN, INT_MAX);
}

// 用值区间(lower,upper)判断A[start..end)
bool verify(vector<int> &A, int start, int end, int lower, int upper) {
    if (start >= end) return true;
    int val = A[start];
    if (val <= lower || val >= upper) return false;
    int i = start + 1;
    while (i < end && A[i] < val) i++;
    if (!verify(A, start + 1, i, lower, val)) return false;
    if (!verify(A, i, end, val, upper)) return false;
    return true;
}

从前序遍历数组构造bst

TreeNode* bstFromPreorder(vector<int>& A) {
    int idx = 0; // 有个idx记录扫描位置，在每个位置检查是否满足upper
    return bstFromPreorder(A, idx, INT_MAX);
}

TreeNode* bstFromPreorder(vector<int>& A, int &idx, int upper) {
    if (idx >= A.size() || A[idx] > upper) return NULL;

    int val = A[idx++];
    auto node = new TreeNode(val);
    node->left = bstFromPreorder(A, idx, val);
    node->right = bstFromPreorder(A, idx, upper);
    return node;
}

bst修剪到[L,R]范围

TreeNode* trimBST(TreeNode* root, int L, int R) {
    if (!root) return NULL;
    if (root->val > R) return trimBST(root->left, L, R);
    if (root->val < L) return trimBST(root->right, L, R);

    root->left = trimBST(root->left, L, R);
    root->right = trimBST(root->right, L, R);
    return root;
}

最大和的bst子树

int maxSumBST(TreeNode* root) {
    int ans = 0;
    dfs(root, ans);
    return ans;
}

// 返回{sum, min, max}
// 空节点作左儿子时，要让"父节点的val > 空节点的max"总成立，空节点的max=INT_MIN；
// 同理，空节点的min=INT_MAX；所以，空节点值区间[INT_MAX,INT_MIN]
// {0,INT_MAX,INT_MIN}表示空节点，{0,INT_MIN,INT_MAX}表示无效节点
array<int,3> dfs(TreeNode *root, int &ans) {
    if (!root) return { 0, INT_MAX, INT_MIN };
    auto left = dfs(root->left, ans);
    auto right = dfs(root->right, ans);
    if (left[2] < root->val && root->val < right[1]) {
        int sum = left[0] + root->val + right[0];
        ans = max(ans, sum);
        return { sum, min(root->val, left[1]), max(root->val, right[2]) };
    }
    return { 0, INT_MIN, INT_MAX };
}

最大bst子树

解法同上题，dfs返回{size, min, max}

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.
Here's an example:

   10
   / \
  5  15
 / \   \ 
1   8   7

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

Hint:

  1. You can recursively use algorithm similar to 98. Validate Binary Search Tree at each node of the tree, which will result in O(nlogn) time complexity.

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