小红的完全二叉树构造
题目描述
小红想构造一个总共 n 个节点完全二叉树，该二叉树满足以下两个性质：
1. 所有节点的权值值为 1 ~ n 的一个排列。
2. 除了根节点以外，每个节点的权值和它父亲的权值的乘积为偶数。
请你帮小红构造出这个二叉树，并按层序遍历的方式打印所有节点。
输入描述:一个正整数 n，代表二叉树的节点数量。2≤n≤10^5;
输出描述:
输出一行n个正整数，代表小红构造的二叉树的层序遍历的序列。
输入 4
输出2 4 3 1
说明这棵树的结构如下
显然，任意节点和它父亲权值的乘积都是偶数。
#include<iostream> #include<algorithm> using namespace std; void solve() { int n, i, j; cin>>n; for (i = 2; i <= n; i += 2) { cout<<i<<' '; } for (i = 1; i <= n; i += 2) { cout<<i<<' '; } cout<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; while (T--) { solve(); } return 0; }
平衡二叉树
题目描述
平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。
给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。
输入描述:两个整数，n, d.
输出描述:一个整数：所有高度为 n 的平衡树中不平衡度的最大值。
输入 4 1
输出 5
说明
下面这棵树在 d=1 的定义下高度是平衡的，其不平衡度为 5。
备注:0 ≤ n, d ≤ 60
#include <iostream> using namespace std; typedef long long ll; class Tree { public: ll left; ll right; }; Tree tree[65]; int main() { tree[1].right = 0; tree[1].left = 0; int n, d; while(cin >> n >> d){ ll l = 1; for (int i = 1; i<n; ++i) { l = l * 2; } --l; for (int i = 2; i <= d+1; ++i) { tree[i].left = i - 1; } for (int i = 2; i + d<n+1; ++i) { tree[i + d].left = tree[i + d - 1].left + tree[i + d - 1].right + 1; tree[i + d].right = tree[i-1].left + tree[i-1].right+1; } cout<< l - tree[n - d].left <<endl; } return 0; }
