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

[编程题]找到二叉树中的最大搜索二叉子树

热度指数：2999 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一颗二叉树，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子树，输出该子树总节点的数量。

搜索二叉树是指对于二叉树的任何一个节点，都大于其左子树中的全部节点，但是小于其右子树中的全部节点。

输入描述:

第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。

以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)

ps:节点的编号就是节点的值。

输出描述:

示例1

输入

输出

算法知识视频讲解

我要出去乱说

发表于 2022-06-22 17:14:36

1、思路需要求出以每一个节点为头节点的子树的最大搜索二叉子树。对于每一个节点，我们用一个结构体ReturnType来保存该节点的四种信息：1、maxBSTHead 该子树中最大二叉搜索树的头节点；2、maxBSTSize 该子树中最大二叉搜索树的节点个数；3、min 该子树中最小节点值；4、ma 展开全文

WYJ96

发表于 2021-07-26 17:06:02

import java.util.*; public class Main { static class Node{ 展开全文

城志

发表于 2020-02-22 15:00:05

【典型】树的动态规划问题 1. 分析树形动态规划问题的前提：如果题目要求的目标是规则S，则流程一般是完成每个结点为root时的子树，在规则S下的每一个答案，最终答案一定在这些答案中。本题中，规则是整棵树的最大搜索二叉树（maxBST）。求出每一个节点作为root的子树的maxBST，最终答案展开全文

WYJ96

发表于 2021-07-26 16:29:54

static class Node{ Node left; Node right; int value; public Node(int value) { this.value = value; 展开全文