题意 你有一棵个节点的二叉树，每个节点有权值，你要选尽量多的点，但是得满足以下限制：对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。 分析 根的值右子树的最大值左子树的最大值，如果要选择最多的点，那么如
展开全文
思路：这个题意我读了半年样例的3是这样的这里为什么不选4号节点呢，因为“如果在左子树选了一个点，在右子树中选的其他点要比它小。”，也就是左子树的值应该比右子树的值大，并且根节点的值最小，那么我们可以知道 根节点<右子树<左子树，那么我们可以根-右-左这样遍历这棵树，然后存他的dfs序，要
展开全文
传送门 注意一下这两句话 如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大； 如果在左子树选了一个点，在右子树中选的其他点要比它小。 根节点比子节点都要小 右子树比左子树都要大 所以可以跑序维护最长上升子序列来写 #include <bits/stdc++.h>
using
展开全文
Description Solution 前置知识：最长上升子序列O(nlogn)的贪心做法, dfs序分析:从题目中可以得出，根 < 右子树 < 左子树，如果要选择最多的点，那么如果能够处理出根 -> 右子树 -> 左子树的dfs序，在序列上取一个最长上升子序列，就能选
展开全文
分析 我们可以发现一个特征：左子树的值当前点值右子树的值这个可以让我们联想到dfn序！随着dfs的进行我们先走完左子树，再走完右子树，最后离开当前节点发现是一个后序遍历的dfn序拉出来之后我们只需要进行一个最长不上升子序列的求解即可树状数组离散化之后维护一下就OK了时间复杂度：期望得分：100分 代
展开全文
做法：dfs序+LIS 思路： 因为这是棵二叉树，所以可以使用结构体存储 由如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大可以得出根节点<左节点，根节点<右节点由如果在左子树选了一个点，在右子树中选的其他点要比它小可以得出右节点<左节点所以根节点<右节点&l
展开全文
题目描述 有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。 对于任意一棵子树，都要满足： 如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大； 如果在左子树选了一个点，在右子树中选的其他点要比它小。 输入描述: 第一行一个
展开全文
选点 题目地址： https://ac.nowcoder.com/acm/problem/22494 基本思路: 我们看到题目给出的条件,要满足这个条件我们可以考虑构造序的访问顺序,我们知道对于一棵子树来说根节点肯定是第一个访问的,那么只要我们先访问右子树再访问左子树,用这样的顺序去构造序列
展开全文
题目： 有一棵个节点的二叉树，为根节点，每个节点有一个值。现在要选出尽量多的点。对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小； 做法： 题意转化一下。“右子树中选的点要比左子树中选的点小”反一下就是
展开全文
题意：有一棵n个节点的二叉树，1为根节点，每个节点有一个值wi。现在要选出尽量多的点。对于任意一棵子树，都要满足：如果选了根节点的话，在这棵子树内选的其他的点都要比根节点的值大；如果在左子树选了一个点，在右子树中选的其他点要比它小。 题解：要满足根节点的值最小，左子树的值大于右子树的值。这样的话我们
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
