二叉树

在二进制世界里, 有很多的树, 比如常见的二叉树
而二叉搜索树是比较特殊的一种二叉树, 对于树上的每个节点
它的权值大于等于它的左子树节点, 小于等于它右子树的节点

现在给你若干个二叉树, 请判断它们是否是二叉搜索树

下面是对二叉树的定义:

二叉树是递归定义的, 逻辑上二叉树有五种基本形态：

1.空二叉树——如图(a);

2.只有一个根结点的二叉树——如图(b);
3.只有左子树——如图(c);

4.只有右子树——如图(d);

5.既有左子树又有右子树——如图(e);
同样的, 左子树和右子树也是一颗二叉树

下面是对二叉搜索树的定义:

1.若任意节点的左子树不空, 则左子树上所有结点的值均小于等于它的根结点的值;

2.若任意节点的右子树不空, 则右子树上所有结点的值均大于等于它的根结点的值;

3.任意节点的左、右子树也分别为二叉查找树

第一行包含一个正整数T, 表示二叉树的个数
接下来有T组数据, 每组数据代表一棵二叉树信息, 格式如下:
每组数据第一行包含两个正整数m和r, 表示树上的节点数量和根节点的标号

接下来的m行按1~m标号, 第i行包含标号为i的节点的信息:
包含三个非负整数v, a, b分别代表该节点的权值, 左儿子的节点标号和右儿子的节点标号(如果某儿子标号为0, 表示不存在该儿子)

保证每组数据给的是一棵二叉树

#include<bits/stdc++.h> using namespace std; const int MAXN = 80001; int L[MAXN]; int R[MAXN]; int W[MAXN]; vector<int> path; void dfs(int s) { if (!s) return; dfs(L[s]); path.push_back(W[s]); dfs(R[s]); } int main(){ int T; cin >> T; while (T--) { int m, r; cin >> m >> r; path.clear(); for (int i = 1; i <= m; i++) cin >> W[i] >> L[i] >> R[i]; dfs(r); if (is_sorted(path.begin(), path.end())) cout << "yes" << endl; else cout << "no" << endl; } }

详情