二叉树

二叉树

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构[1]。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒

二叉树深度

https://www.luogu.com.cn/problem/P4913

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

const int N = 1e6 + 10;
/*

       1
     /   \
    2     7
   / \
  3   6
 / \
4   5

从结点1开始，深度为1。
访问结点2（深度2），然后递归遍历结点2的左右子结点。
访问结点3（深度3），递归遍历结点3的左右子结点。
访问结点4（深度4），结点4没有子结点，回溯。
访问结点5（深度4），结点5没有子结点，回溯。
访问结点6（深度3），结点6没有子结点，回溯。
访问结点7（深度2），结点7没有子结点，回溯。

*/
struct node{
	int l, r;
} tree[N];

int n, ans;

void dfs(int id, int deep) {
	if (id == 0) return;
	ans = max(ans, deep);
	dfs(tree[id].l, deep + 1);
	dfs(tree[id].r, deep + 1);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> tree[i].l >> tree[i].r;
	dfs(1, 1);
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}

求先序排列

https://www.luogu.com.cn/problem/solution/P1030

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

/*
      F
     / \
    B   G
   / \   \
  A   D    I
     / \   /
    C   E  H


1. 先序遍历

根 -> 左 -> 右(看成一直向左偏)
F B A D C E G I H


2. 中序遍历

左 -> 根 -> 右
A B C D E F G H I


3. 后序遍历

左 -> 右 -> 根
A C E D B H I G F
*/

// 后序遍历最后一个就是根，先序就是不断找根
// step1:找到根并输出
// step2:将中序，后序各分为左右两棵子树；
// step3:递归，重复step1,2

string preorder;

void dfs(string inorder, string postorder) {
	if (inorder.size() == 0) return;
	char ch = postorder.back();
	preorder += ch;
	// 找到根节点在中序遍历中的位置
	int pos = inorder.find(ch);
	// 递归处理左子树
	dfs(inorder.substr(0, pos), postorder.substr(0, pos));
	// 递归处理右子树
	dfs(inorder.substr(pos + 1), postorder.substr(pos, inorder.size() - pos - 1));
}


void solve() {
	string inorder, postorder;
	cin >> inorder >> postorder;
	dfs(inorder, postorder);
	cout << preorder << endl;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin >> t;
	while (t--) {
		solve();
	}
	
	return 0;
}