心双2024数据结构1044-1049题解-xiwwwix's blog

1044-1049是树的题目
树的部分要重点掌握以下几个东西：

邻接表存图（建议直接用C++的二维vector）
树上的深度优先和广度优先遍历（前者可以理解成：一直向下找，一条路走到黑，直到叶子结点；后者则是“一层一层走”，先走根，再走根的儿子们，然后是儿子的儿子……）
前序+中序/中序+后序还原二叉树（重要，难但是会考）

1044. 树的双亲存储法

用C++的二维vector存树可以极简地理解成这么一回事：
vector<vector<int>> children(n);这行代码用于声明一个二维向量（理解成不定长数组就可以），也可以看成一个长度为n的数组children，数组里面的n个元素的类型是什么呢？比较特殊，还是一个数组（也就是<>里面的那个vector<int>）

这样，我们就可以用children[i]表示树上编号为i的结点的儿子们，因为children[i]还是一个不定长的数组，我们每次得到一个它的新的儿子，就往这个数组的“最后”那里放进去就可以了（对应代码里的push_back函数）

代码里dfs（深度优先遍历）又是在干什么呢？对于每个结点node，我们先对它的所有儿子继续进行dfs操作，然后把node放进答案里

一些同学可能觉得这个递归的操作比较难理解，我的建议是：不要过度陷入思考递归细节的过程当中，其实你要做的事情只是：

知道你的递归函数“每一层在干什么”，比如我们这个dfs就是在“遍历某个结点的儿子，对儿子dfs，然后把自己放进答案”
考虑一下边界情况：递归终止，或者说不会再继续调用这个递归函数的最终情况，比如说dfs里的遍历，如果没有儿子，当然就不用遍历，就不会再有下一步的dfs
结束了，大胆相信你的递归函数真的能实现以上功能，你的重点就是“怎么递推到下一层 + 递归终止条件”
实在不行的话，就先把这个dfs函数背下来，多敲几遍一样的代码也许就顿悟了（

#include <bits/stdc++.h>
using namespace std;

void dfs(int node, const vector<vector<int>>& children, vector<int>& result) {
	for (int child : children[node]) {
		dfs(child, children, result);
	}
	result.push_back(node);
}

int main() {
	int n;
	cin >> n;
	vector<int> parent(n);
	for (int i = 0; i < n; i++) {
		cin >> parent[i];
	}
	vector<vector<int>> children(n);
	for (int i = 0; i < n; i++) {
		if (parent[i] != -1) {
			children[parent[i]].push_back(i);
		}
	}
	vector<int> result;
	dfs(0, children, result);

	for (int node : result) {
		cout<<node<< " ";
	}
	cout<<endl;

	return 0;
}

1045. 树的相关操作

要素齐全，个人感觉有两个小的知识点：

前序遍历（preorder）和后序遍历（postorder）的区别其实就只有一个：函数里是先输出再遍历，还是先遍历再输出
层序遍历使用了STL的queue实现，非常的方便（赞赏），思路就是：只要队列非空，每次读取队首并输出，把队首结点的儿子们放在队尾，再去掉队首，这样就能保证：每一层结点的儿子们一定是在这一层结点之后才被输出的

#include <bits/stdc++.h>
using namespace std;

int cnt1 = 0;
int cnt2 = 0;
int height = 0;

void preorder(int node,vector<vector<int>>& tree) {
	cout << node << " ";
	for (auto son:tree[node]) {
		preorder(son,tree);
	}
}

void postorder(int node,vector<vector<int>>& tree) {
	for (auto son:tree[node]) {
		postorder(son,tree);
	}
	cout << node << " ";
}

void BFS(int root,vector<vector<int>>& tree) {
	queue<int> q;
	q.push(root);
	cnt1++;
	while (!q.empty()) {
		int node = q.front();
		q.pop();
		cout << node << " ";
		for (auto son:tree[node]) {
			q.push(son);
			cnt1++;
		}
	}
}

void count(int node,vector<vector<int>>& tree,int h) {
	if (tree[node].size() == 0) {
		cnt2++;
		cout << node << " ";
		height = max(h,height);
	}
	for (auto son:tree[node]) {
		count(son,tree,h+1);
	}
}

int main() {
	vector<vector<int>> tree(1001);
	int root;
	int a,b;
	while (cin >> a >> b) {
		if (b == -1) {
			root = a;
		} else {
			tree[b].push_back(a);
		}
	}
	
	preorder(root,tree);
	cout << endl;
	
	postorder(root,tree);
	cout << endl;
	
	BFS(root,tree);
	cout << endl;
	cout << cnt1 << endl;
	
	count(root,tree,0);
	cout << endl;
	
	cout << cnt2 << endl;
	cout << height << endl;
	
	return 0;
}

1046. 还原二叉树

根据先序+中序还原二叉树
计算高度（dfs，递归比较左右子树大小，取较大的）

#include <bits/stdc++.h>
using namespace std;
char pre[51];
char mid[51];

struct node {
	char data;
	node* l = nullptr;
	node* r = nullptr;
};

void build(node* &root,char* pre,char* mid,int len) {
	root = new node;
	if (root != nullptr) {
		if (len <= 0) {
			root = nullptr;
			return;
		}
		int idx = 0;
		while (idx < len && *(pre) != *(mid + idx)) {
			idx++;
		}
		root->data = *(pre);
		build(root->l,pre+1,mid,idx);
		build(root->r,pre+1+idx,mid+1+idx,len-idx-1);
	}
	return;
}

int dfs(node* root) {
	if (root == nullptr) {
		return 0;
	}
	int lh = dfs(root->l);
	int rh = dfs(root->r);
	int height = max(lh,rh) + 1;
	return height;
}

int main() {
	int n;
	cin >> n;
	cin >> pre >> mid;
	node* tree;
	build(tree,pre,mid,n);
	cout << dfs(tree) << endl; 
	return 0;
}

每次需要在中序遍历序列中查找根节点的位置，一共n个节点，对于每个节点，递归调用会处理其左子树和右子树，所以总时间复杂度为O(n^2)（最坏情况下，树会退化为一条链）

1047. 最小权值路径

隐约记得写过两个版本，后面那个码风很好，但是找不到了。。。第一个版本我现在自己也没看太懂，怀疑当时是gpt写的（私密马赛

#include <bits/stdc++.h>
using namespace std;

struct Node {
	int val;
	Node* left;
	Node* right;
	Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* build(vector<int>& in, vector<int>& post, unordered_map<int, int>& m, int s, int e, int& p) {
	if(s > e) return nullptr;
	int rootVal = post[p];
	Node* root = new Node(rootVal);
	int idx = m[rootVal];
	p--;
	root->right = build(in, post, m, idx+1, e, p);
	root->left = build(in, post, m, s, idx-1, p);
	return root;
}

pair<long long, int> findMin(Node* root) {
	long long minSum = LLONG_MAX;
	int leafVal = INT32_MAX;
	stack<pair<Node*, long long>> stk;
	stk.push(make_pair(root, 0));
	while(!stk.empty()) {
		pair<Node*, long long> current = stk.top();
		stk.pop();
		Node* node = current.first;
		long long sum = current.second;
		if(!node) continue;
		long long currentSum = sum + node->val;
		if(!node->left && !node->right) {
			if(currentSum < minSum || (currentSum == minSum && node->val < leafVal)) {
				minSum = currentSum;
				leafVal = node->val;
			}
		}
		stk.push(make_pair(node->right, currentSum));
		stk.push(make_pair(node->left, currentSum));
	}
	return make_pair(minSum, leafVal);
}

int main() {
	string inStr, postStr;
	getline(cin, inStr);
	getline(cin, postStr);
	vector<int> in, post;
	int num;
	stringstream ss(inStr);
	while(ss >> num) {
		in.push_back(num);
	}
	stringstream sp(postStr);
	while(sp >> num) {
		post.push_back(num);
	}
	unordered_map<int, int> m;
	for(int i=0; i<in.size(); i++) {
		m[in[i]] = i;
	}
	int pIdx = post.size()-1;
	Node* root = build(in, post, m, 0, in.size()-1, pIdx);
	pair<long long, int> res = findMin(root);
	cout << res.second;
}

因为用了栈，重建二叉树和DFS遍历的时间复杂度均为O(n)

1048. 下落的小球

更像是一道思维题而非数据结构题，纯粹根据题意模拟应该也能过，更好一点的方法是根据输入的小球的奇偶性直接模拟该小球的掉落，不需要把之前小球的掉落过程都求出来。

代码实现的话就是：如果某结点被奇数次经过，走左边（乘2），否则走右边（乘2加1）

原题：https://www.luogu.com.cn/problem/UVA679
可以看看题解区大佬的做法

#include <bits/stdc++.h>
using namespace std;

void solve() {
	int d,c;
	int cur = 1;
	cin >> d >> c;
	for(int i = 1; i < d; i++)
		if (c&1) {
			cur <<= 1; //模拟走过奇数次，乘2
			c = (c >> 1) + 1;
		} else {
			cur <<= 1; 
			cur++; //模拟走过偶数次，乘2再加1
			c >>= 1;
		}
	cout << cur << endl;
}

int main() {
	int t;
	cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}