题解 | 找到二叉树中的最大搜索二叉子树

// 作者: Jacobzp
// 指导老师: 左程云老师
// 学习视频: bilibili 算法讲解078【必备】树形dp-上
#include <bits/stdc++.h>
#include <limits>
using namespace std;
#define int long long
#define endl '\n'

int n, root;

struct TreeNode {
    int val;
    int lid, rid;
    bool isExist;
} node[1000005];

struct Info {
    int max_val, min_val;
    bool isBst;
    int maxBstSize;
    Info(int a, int b, bool c, int d) {
        max_val = a, min_val = b, isBst = c, maxBstSize = d;
    }
};

Info f(TreeNode x) {
    if (!x.isExist) {
        return Info(numeric_limits<int>::min(), numeric_limits<int>::max(), true, 0);
    }
    Info l = f(node[x.lid]), r = f(node[x.rid]);
    int max_val = max(x.val, max(l.max_val, r.max_val));
    int min_val = min(x.val, min(l.min_val, r.min_val));
    bool isBst = l.isBst && r.isBst && l.max_val<x.val && x.val<r.min_val;
    int maxBstSize;
    if (isBst) {
        maxBstSize = l.maxBstSize + r.maxBstSize + 1;
    }
    else {
        maxBstSize = max(l.maxBstSize, r.maxBstSize);
    }
    return Info(max_val, min_val, isBst, maxBstSize);
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> root;
    for (int i = 1; i <= n; i++) {
        int fa, lid, rid;
        cin >> fa >> lid >> rid;
        node[fa].val = fa, node[lid].val = lid, node[rid].val = rid;
        node[fa].lid = lid, node[fa].rid = rid;
        node[fa].isExist = true;
        if (lid != 0) node[lid].isExist = true;
        if (rid != 0) node[rid].isExist = true;
    }
    cout << (f(node[root])).maxBstSize << endl;
}