给定一颗二叉树，已知其中所有节点的值都不一样，找到含有节点最多的搜索二叉子树，输出该子树总节点的数量。
搜索二叉树是指对于二叉树的任何一个节点，都大于其左子树中的全部节点，但是小于其右子树中的全部节点。
[编程题]找到二叉树中的最大搜索二叉子树
- 热度指数：3050 时间限制：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
输入
3 2 2 1 3 1 0 0 3 0 0
输出
3
树型DP，使用二叉树的递归套路，根据是否要将当前结点纳入搜索二叉树划分可能性。需要向左子树和右子树要五个信息：
- 子树的最大二叉搜索树的根结点；
- 子树的最大二叉搜索树的节点数量；
- 子树是否是二叉搜索树；
- 子树的节点最小值；
- 子树的节点最大值。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
class Info {
public TreeNode maxBSTHead;
public int maxBSTSize;
public boolean isBST;
public int min;
public int max;
public Info(TreeNode maxBSTHead, int maxBSTSize, boolean isBST, int min, int max) {
this.maxBSTHead = maxBSTHead;
this.maxBSTSize = maxBSTSize;
this.isBST = isBST;
this.min = min;
this.max = max;
}
}
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashMap<Integer, TreeNode> map = new HashMap<>();
String[] params = br.readLine().split(" ");
int n = Integer.parseInt(params[0]), rootVal = Integer.parseInt(params[1]);
// 构建二叉树
TreeNode root = new TreeNode(rootVal);
map.put(rootVal, root);
for(int i = 0; i < n; i++){
params = br.readLine().split(" ");
int nodeVal = Integer.parseInt(params[0]);
int leftVal = Integer.parseInt(params[1]);
int rightVal = Integer.parseInt(params[2]);
TreeNode node = map.get(nodeVal);
if(leftVal != 0) {
node.left = new TreeNode(leftVal);
map.put(leftVal, node.left);
}
if(rightVal != 0) {
node.right = new TreeNode(rightVal);
map.put(rightVal, node.right);
}
}
// 求解
System.out.println(process(root).maxBSTSize);
}
private static Info process(TreeNode node) {
if(node == null) return null;
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
TreeNode maxBSTHead = null;
int maxBSTSize = 0;
int max = node.val;
int min = node.val;
// 最值在左右信息不为空的时候需要比较更新
if(leftInfo != null){
maxBSTHead = leftInfo.maxBSTHead;
maxBSTSize = leftInfo.maxBSTSize;
max = Math.max(max, leftInfo.max);
min = Math.min(min, leftInfo.min);
}
if(rightInfo != null){
if(rightInfo.maxBSTSize > maxBSTSize){
maxBSTHead = rightInfo.maxBSTHead;
maxBSTSize = rightInfo.maxBSTSize;
}
max = Math.max(max, rightInfo.max);
min = Math.min(min, rightInfo.min);
}
boolean isBST = false;
// 左右子树都是BST且能够和当前节点连起来时，能够形成一个以当前节点为根的更大的BST
if((leftInfo == null || (leftInfo.isBST && leftInfo.max < node.val)) && (rightInfo == null || (rightInfo.isBST && rightInfo.min > node.val))){
isBST = true;
maxBSTHead = node;
maxBSTSize = (leftInfo != null? leftInfo.maxBSTSize: 0) + (rightInfo != null? rightInfo.maxBSTSize: 0) + 1;
}
return new Info(maxBSTHead, maxBSTSize, isBST, min, max);
}
}
发表于 2021-11-26 18:47:35
回复(0)
很好理解，但是时间复杂度比较高
import java.util.HashMap;
import java.util.Scanner;
/**
* @Author fgf
* @create 2020/3/10 22:12
* 找到二叉树中的最大搜索二叉之树
*/
class Node {
public int value;
public Node left;
public Node right;
public Node(int data){
this.value = data;
}
}
public class Main {
private static Node bstNode = null;
private static int max = Integer.MIN_VALUE;
private static int pre = Integer.MIN_VALUE;
public static void getMaxBST(Node root){
if(root == null)
return;
pre = Integer.MIN_VALUE;
if(isBST(root)){
int nodesNum = getNodesNum(root);
if(nodesNum > max){
max = nodesNum;
bstNode = root;
}
}
getMaxBST(root.left);
getMaxBST(root.right);
}
//获得二叉树节点个数
public static int getNodesNum(Node root){
if(root == null)
return 0;
return 1 + getNodesNum(root.left) + getNodesNum(root.right);
}
//判断是否是一颗搜索二叉树 中序遍历 左中右
public static boolean isBST(Node root){
if(root == null)
return true;
boolean flagLeft = isBST(root.left);
if(pre >= root.value)
return false;
pre = root.value;
if(flagLeft == false)
return false;
else
return isBST(root.right);
}
public static void main(String[] args) {
/**
13 6
6 1 12
1 -1 3
12 10 13
-1 0 0
3 0 0
10 4 14
13 20 16
4 2 5
14 11 15
2 0 0
5 0 0
11 0 0
15 0 0
*/
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
Node root = new Node(scanner.nextInt());
HashMap<Integer, Node> hashMap = new HashMap<>();
hashMap.put(root.value, root);
int[][] nodes = new int[count][3];
for(int i=0; i<count; i++){
for(int j=0; j<3; j++){
int v = scanner.nextInt();
if(v != 0)
hashMap.put(v, new Node(v));
nodes[i][j] = v;
}
}
for(int i=0; i<count; i++){
int[] arr = nodes[i];
Node fakeRoot = hashMap.get(arr[0]);
if(arr[1] != 0)
fakeRoot.left = hashMap.get(arr[1]);
if(arr[2] != 0)
fakeRoot.right = hashMap.get(arr[2]);
}
root = hashMap.get(root.value);
getMaxBST(root);
System.out.println(max);
// System.out.println(bstNode.value);
// System.out.println(isBST(root));
}
}
发表于 2020-03-10 23:03:05
回复(0)
//参考左神的📕
#include<iostream>
#include<climits> using namespace std;
//树节点
struct TreeNode{int val;
TreeNode* left;
TreeNode* right;
};
树dp的信息
struct BSTtype{TreeNode* pBSTHead;
int BSTsize;
int valmax;
int valmin;
BSTtype(TreeNode* _pBSTHead,int _BSTsize,int _valmax,int _valmin){
pBSTHead = _pBSTHead;
BSTsize = _BSTsize;
valmax = _valmax;
valmin = _valmin;
}
};
//递归过程
BSTtype process(TreeNode* pRoot){if(pRoot==nullptr){
return BSTtype(nullptr,0,INT_MIN,INT_MAX);
}
BSTtype lnode =process(pRoot->left);
BSTtype rnode =process(pRoot->right);
int curmax = max(pRoot->val,max(lnode.valmax,rnode.valmax));
int curmin = min(pRoot->val,min(lnode.valmin,rnode.valmin));
int cursize =max(lnode.BSTsize,rnode.BSTsize);
TreeNode* pCurHead = lnode.BSTsize>rnode.BSTsize?lnode.pBSTHead:rnode.pBSTHead;
if(pRoot->left == lnode.pBSTHead && pRoot->right==rnode.pBSTHead && lnode.valmax < pRoot->val&& rnode.valmin > pRoot->val){
pCurHead = pRoot;
cursize = lnode.BSTsize+rnode.BSTsize+1;
}
return BSTtype(pCurHead,cursize,curmax,curmin);
}
//创建树
void createTree(TreeNode* pRoot,int& n){if(n==0){
return;
}
int rootval,leftval,rightval;
cin>>rootval>>leftval>>rightval;
if(leftval!=0){
TreeNode* leftnode = new TreeNode;
leftnode->val = leftval;
leftnode->left =leftnode->right=nullptr;
pRoot->left = leftnode;
createTree(leftnode,--n);
}
if(rightval!=0){
TreeNode* rightnode = new TreeNode;
rightnode->val = rightval;
rightnode->left =rightnode->right=nullptr;
pRoot->right = rightnode;
createTree(rightnode,--n);
}
}
int main(){
int n,rootval;
cin>>n>>rootval;
TreeNode* pRoot = new TreeNode;
pRoot->val = rootval;
pRoot->left = pRoot->right = nullptr;
TreeNode* pCurrnode =pRoot;
while(n--){
createTree(pCurrnode,n);
}
BSTtype res = process(pCurrnode);
cout<<res.BSTsize<<endl;
return 0;
}
发表于 2020-07-27 20:02:11
回复(0)
#include<bits/stdc++.h>
using namespace std;
struct ReturnType{
int maxBSTHead;
int maxBSTSize;
int MIN;
int MAX;
ReturnType(int root,int size,int Min,int Max):maxBSTHead(root),maxBSTSize(si***(Min),MAX(Max){}
};
ReturnType process(int root,int* lc,int* rc)
{
// base case 注意最大最小值的赋值
if(!root) return ReturnType(0,0,INT_MAX,INT_MIN);
// 搜集到左右子树的信息
ReturnType ldata = process(lc[root],lc,rc);
ReturnType rdata = process(rc[root],lc,rc);
// 整合
// 以当前结点为根的最大值与最小值
int max_ = max(root,max(ldata.MAX,rdata.MAX));
int min_ = min(root,min(ldata.MIN,rdata.MIN));
// 最大搜索二叉子树来源于左子树或右子树
int curMaxBSTHead = ldata.maxBSTSize>rdata.maxBSTSize ? ldata.maxBSTHead:rdata.maxBSTHead;
int curMaxBSTSize = max(ldata.maxBSTSize,rdata.maxBSTSize);
// 要把根节点加入进去的情况
if(ldata.maxBSTHead == lc[root] && rdata.maxBSTHead == rc[root] && root>ldata.MAX && root<rdata.MIN)
{
curMaxBSTHead = root;
curMaxBSTSize = 1 + ldata.maxBSTSize + rdata.maxBSTSize;
}
return ReturnType(curMaxBSTHead,curMaxBSTSi***_,max_);
}
int main()
{
int n,root;
cin>>n>>root;
int* lc = new int[n+1];
int* rc = new int[n+1];
int p;
for(int i=0;i<n;++i)
{
cin>>p;
cin>>lc[p]>>rc[p];
}
int ans = process(root,lc,rc).maxBSTSize;
cout<<ans<<endl;
return 0;
}
编辑于 2020-02-05 11:10:25
回复(0)
import java.lang.Math;
import java.util.Scanner;
import java.util.HashMap;
class Info{
boolean flag = true;
int nodesNum = 0;
}
class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
}
public class Main{
public static void main(String[] args){
HashMap<Integer, Node> map = new HashMap<>();
Scanner sc = new Scanner(System.in);
String firstLine = sc.nextLine();
String[] params = firstLine.split(" ");
int n = Integer.valueOf(params[0]);
int rootVal = Integer.valueOf(params[1]);
Node root = new Node(rootVal);
map.put(rootVal, root);
//构建二叉树
for(int i=0; i<n; i++){
String line = sc.nextLine();
String[] str = line.split(" ");
int faVal = Integer.valueOf(str[0]);
int lchVal = Integer.valueOf(str[1]);
int rchVal = Integer.valueOf(str[2]);
Node curNode = map.get(faVal);
if(lchVal != 0){
curNode.left = new Node(lchVal);
map.put(lchVal, curNode.left);
}
if(rchVal != 0){
curNode.right = new Node(rchVal);
map.put(rchVal, curNode.right);
}
}
Info info = process(root);
System.out.println(info.nodesNum);
}
public static Info process(Node node){
Info curInfo = new Info();
if(node == null){
return curInfo;
}
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
if(((leftInfo.flag && rightInfo.flag) != true) ||
(node.left != null && getTreeMaxValue(node.left)>node.value) ||
(node.right != null && getTreeMinValue(node.right)<node.value)){
curInfo.flag = false;
curInfo.nodesNum = Math.max(leftInfo.nodesNum, rightInfo.nodesNum);
return curInfo;
}
curInfo.nodesNum = leftInfo.nodesNum + rightInfo.nodesNum + 1;
return curInfo;
}
public static int getTreeMaxValue(Node node){
while(node.right != null){
node = node.right;
}
return node.value;
}
public static int getTreeMinValue(Node node){
while(node.left != null){
node = node.left;
}
return node.value;
}
} import java.lang.Math;
import java.util.Scanner;
import java.util.HashMap;
class Info{
boolean flag = true;
int nodesNum = 0;
int max;
int min;
}
class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
}
}
public class Main{
public static void main(String[] args){
HashMap<Integer, Node> map = new HashMap<>();
Scanner sc = new Scanner(System.in);
String firstLine = sc.nextLine();
String[] params = firstLine.split(" ");
int n = Integer.valueOf(params[0]);
int rootVal = Integer.valueOf(params[1]);
Node root = new Node(rootVal);
map.put(rootVal, root);
//构建二叉树
for(int i=0; i<n; i++){
String line = sc.nextLine();
String[] str = line.split(" ");
int faVal = Integer.valueOf(str[0]);
int lchVal = Integer.valueOf(str[1]);
int rchVal = Integer.valueOf(str[2]);
Node curNode = map.get(faVal);
if(lchVal != 0){
curNode.left = new Node(lchVal);
map.put(lchVal, curNode.left);
}
if(rchVal != 0){
curNode.right = new Node(rchVal);
map.put(rchVal, curNode.right);
}
}
Info info = process(root);
System.out.println(info.nodesNum);
}
public static Info process(Node node){
Info curInfo = new Info();
if(node == null){
return curInfo;
}
Info leftInfo = process(node.left);
Info rightInfo = process(node.right);
curInfo.max = node.right==null ? node.value : rightInfo.max;
curInfo.min = node.left==null ? node.value : leftInfo.min;
if(((leftInfo.flag && rightInfo.flag) != true) ||
(node.left != null && leftInfo.max>node.value) ||
(node.right != null && rightInfo.min<node.value)){
curInfo.flag = false;
curInfo.nodesNum = Math.max(leftInfo.nodesNum, rightInfo.nodesNum);
return curInfo;
}
curInfo.nodesNum = leftInfo.nodesNum + rightInfo.nodesNum + 1;
return curInfo;
}
}
编辑于 2022-05-24 22:22:40
回复(0)
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
class TreeNode{
public:
int val;
TreeNode* left, * right;
TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr):
val(val), left(left), right(right){}
};
class Solution{
public:
static bool checkRoot(TreeNode* root, TreeNode* left, TreeNode* right){
while(right != nullptr && right->left != nullptr) right = right->left;
while(left != nullptr && left->right != nullptr) left = left->right;
if((left == nullptr || left->val < root->val) &&
(right == nullptr || right->val > root->val)){
return true;
}
return false;
}
static pair<int, TreeNode*> getMaxBSTree(TreeNode* root){
if(root == nullptr) return make_pair(0, nullptr);
int rootResSize = 0;
pair<int, TreeNode*> rootRes;
pair<int, TreeNode*> leftRes = getMaxBSTree(root->left);
pair<int, TreeNode*> rightRes = getMaxBSTree(root->right);
if (leftRes.second == root->left && rightRes.second == root->right
&& checkRoot(root, root->left, root->right)){
rootResSize = leftRes.first + rightRes.first + 1;
rootRes.first = rootResSize;
rootRes.second = root;
}else{
rootRes = leftRes.first > rightRes.first ? leftRes : rightRes;
}
return rootRes;
}
};
int main(){
int n, rootVal;
int line[3];
TreeNode* root = nullptr;
unordered_map<int, TreeNode*> treeNodes;
treeNodes.insert(make_pair(0, nullptr));
cin >> n >> rootVal;
while(n--){
cin >> line[0] >> line[1] >> line[2];
for(int i = 0; i < 3; i++){
if(treeNodes.count(line[i]) == 0){
treeNodes.insert(make_pair(line[i], new TreeNode(line[i])));
}
}
treeNodes[line[0]]->left = treeNodes[line[1]];
treeNodes[line[0]]->right = treeNodes[line[2]];
}
root = treeNodes[rootVal];
cout << Solution::getMaxBSTree(root).first;
return 0;
}
发表于 2021-09-21 16:03:20
回复(0)
import java.util.*;
class Node {
public int val;
public Node right;
public Node left;
public Node (int val) {
this.val = val;
}
}
class ReturnType {
public Node maxBSTHead;
public int maxBSTSize;
public int max;
public int min;
public ReturnType(Node maxBSTHead, int maxBSTSize, int min, int max) {
this.maxBSTHead = maxBSTHead;
this.maxBSTSize = maxBSTSize;
this.min = min;
this.max = max;
}
}
public class Main {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node head = constructTree(sc, n);
int result = returnSize(head);
System.out.println(result);
}
public static Node constructTree (Scanner sc, int n) {
HashMap<Integer, Node> map = new HashMap<>();
int rootVal = sc.nextInt();
Node root = new Node(rootVal);
map.put(rootVal, root);
for (int i = 0; i < n; i++) {
int nodeVal = sc.nextInt();
int leftVal = sc.nextInt();
int rightVal = sc.nextInt();
if (map.containsKey(nodeVal)) {
Node tmpNode = map.get(nodeVal);
Node leftNode = leftVal == 0 ? null : new Node(leftVal);
Node rightNode = rightVal == 0 ? null : new Node(rightVal);
tmpNode.left = leftNode;
tmpNode.right = rightNode;
if (leftVal != 0)
map.put(leftVal, leftNode);
if (rightVal != 0)
map.put(rightVal, rightNode);
}
}
return root;
}
public static int returnSize (Node head) {
return process(head).maxBSTSize;
}
public static ReturnType process (Node x) {
//base case：最小值是系统最大，最大值是系统最小
if (x == null)
return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
//默认直接得到左右树全部信息
ReturnType leftData = process(x.left);
ReturnType rightData = process(x.right);
//信息整合：
/*
同时对以x为头的子树也做同样要求，也需要返回如ReturnType描述的全部信息
*/
int min = Math.min(x.val, Math.min(leftData.min, rightData.min));
int max = Math.max(x.val, Math.max(leftData.max, rightData.max));
int maxBSTSize = Math.max(leftData.maxBSTSize, rightData.maxBSTSize);
Node maxBSTHead = leftData.maxBSTSize >= rightData.maxBSTSize ? leftData.maxBSTHead: rightData.maxBSTHead;
if (leftData.maxBSTHead == x.left && rightData.maxBSTHead == x.right && x.val > leftData.max && x.val < rightData.min) {
maxBSTSize = leftData.maxBSTSize + rightData.maxBSTSize + 1;
maxBSTHead = x;
}
return new ReturnType(maxBSTHead, maxBSTSize, min, max);
}
}
发表于 2021-06-13 20:49:34
回复(0)
//参考左神
import java.util.*;
public class Main{
static class Node{
int key;
Node left;
Node right;
Node(int k){key = k;}
}
static Map<Integer, Node> map = new HashMap<>();
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
//0->size; 1->min; 2->max
int[] record = new int[3];
int n = sc.nextInt(), rootVal = sc.nextInt();
Node root = new Node(rootVal);
map.put(rootVal, root);
while(sc.hasNext()){
int father = sc.nextInt();
int leftV = sc.nextInt(), rightV = sc.nextInt();
Node left = leftV == 0 ? null : new Node(leftV);
if(left != null) map.put(left.key, left);
Node right = rightV == 0 ? null : new Node(rightV);
if(right != null)map.put(right.key, right);
Node f = map.get(father);
f.left = left;
f.right = right;
}
posOrder(root, record);
System.out.print(record[0]);
}
static Node posOrder(Node head, int[]record){
if(head == null){
record[0] = 0;
record[1] = Integer.MAX_VALUE;
record[2] = Integer.MIN_VALUE;
return null;
}
int val = head.key;
Node lBst = posOrder(head.left, record);
int lSize = record[0], lMin = record[1], lMax = record[2];
Node rBst = posOrder(head.right, record);
int rSize = record[0], rMin = record[1], rMax = record[2];
record[1] = Math.min(lMin, val);
record[2] = Math.max(rMax, val);
if(lBst == head.left && rBst == head.right && val > lMax && val < rMin){
record[0] = lSize + rSize + 1;
return head;
}
record[0] = Math.max(lSize, rSize);
return lSize > rSize ? lBst : rBst;
}
}
发表于 2020-08-26 11:43:15
回复(0)
#include <bits/stdc++.h>
#define maxn 1000001
using namespace std;
struct Node{
int val;
Node* left;
Node* right;
};
Node nodes[maxn];
struct Data{
int min;
int max;
int size;
Node* head;
Data(int mi, int ma, int nod, Node* hea){
min = mi;
max = ma;
size = nod;
head = hea;
}
};
Data process(Node* root){
if(root == NULL){
return Data(INT_MAX, INT_MIN, 0, root);
}
Data leftNode = process(root->left);
Data rightNode = process(root->right);
int together = 0;
if(leftNode.head == root->left
&& rightNode.head == root->right
&& leftNode.max < root->val
&& rightNode.min > root->val
) {
together = leftNode.size + rightNode.size + 1;
}
int maxSize = max(max(leftNode.size, rightNode.size), together);
Node* maxHead = leftNode.size > rightNode.size ? leftNode.head : rightNode.head;
if(maxSize == together) {
maxHead = root;
}
return Data(min(min(leftNode.min,rightNode.min),root->val),
max(max(leftNode.max,rightNode.max),root->val),
maxSize,
maxHead);
}
int main()
{
int n,r;
scanf("%d%d",&n,&r);
for(int i=0;i<n;i++){
int index,left,right;
scanf("%d%d%d",&index,&left,&right);
nodes[index].val = index;
if(left)
nodes[index].left = &nodes[left];
else
nodes[index].left = NULL;
if(right)
nodes[index].right = &nodes[right];
else
nodes[index].right = NULL;
}
int res = process(&nodes[r]).size;
printf("%d\n",res);
return 0;
}
发表于 2020-02-08 21:00:01
回复(1)
问题信息
通过挑战的用户
查看代码-
2023-03-05 11:19:40
-
2023-03-01 11:22:44
-
2022-11-08 23:26:08 -
2022-10-26 23:45:52
-
2022-10-09 20:21:37
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
