P996 二叉搜索树 - 复旦2020 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2023年3月23日 21:23

这题的正解是o(n)

P996

回复 1 | 赞 41 | 浏览 4.6k

这个题目做法是o(n)的，但是网上流传了大量o(nlogn)甚至o(n^2)的伪算法首先，二叉搜索树的所有节点是从左到右的，按顺序插入的节点一定不可能排在父节点前面。于是我们将节点放在二维平面内，a[i]坐标为(a[i],i)，i越小，高度越高可以证明两个结论： 1.二叉查找树两个节点i,j若互相不为对方的祖先，则有最近公共祖先x，a[i]与a[j]一个比a[x]大，一个比a[x]小。反证：如果两个都比a[x]大或者比a[x]小，则两个节点在x的同一个子树中，x不是最近公共祖先。 2.数值上处于任何一个节点的父节点及其本身之间的所有节点都是其子...

2026年2月28日 19:42

二叉搜索树 - 复旦2020 题解：

P996

回复 0 | 赞 6 | 浏览 225

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef struct BTNode { int data; struct BTNode* lchild; struct BTNode* rchild; }BTNode,*BiTree; //构建一颗二叉搜索树 BiTree createBST(BiTree T, int key,in...

2026年2月28日 18:53

二叉搜索树 - 复旦2020 题解：

P996

回复 0 | 赞 8 | 浏览 195

只能过90% #include<bits/stdc++.h> using namespace std; typedef struct node{ int data; node* left; node* right; node* father; }*BiTree; BiTree build(BiTree root,int x,BiTree father){ if(root == nullptr){ BiTree t = new node; t->left = nullptr; t->right = nu...

2024年4月8日 09:36

二叉搜索树 - 复旦2020 题解：Time Limit Exceed

P996

回复 3 | 赞 18 | 浏览 2.7k

#include<bits/stdc++.h> using namespace std; int temp[100001]; struct Tree { int data; struct Tree* lchild; struct Tree* rchild; }; //二叉搜索树插入 void _insert(struct Tree* &root, int t) { if(root == NULL) { root = new Tree; root->data = t; ...

题目二叉搜索树 - 复旦2020

题解数量4

发布题解在线答疑

热门题解

1 这题的正解是o(n)

2 二叉搜索树 - 复旦2020 题解：Time Limit Exceeded 90% 有什么办法可以缩短时间呢

3 二叉搜索树 - 复旦2020 题解：

4 二叉搜索树 - 复旦2020 题解：