给定一棵二叉搜索树和一个定值,将该树分成两棵独立的二叉搜索树,要求小于给定值的树节点在一颗树上,不小于给定值的树节点在另一棵二叉树上。语言不限。
第一行两个正整数n,v(1<=n<=100000, 1<=v<=100000),分别表示二叉树的结点数以及给定值。
接下来n行,每行三个整数li,ri,vi,表示二叉搜索树上第i个结点的左儿子编号(0为空),右儿子编号(0为空)以及权值。
保证二叉树合法(对于所有结点有:左子树权值<=根权值<=右子树权值)。
输出n行,第i行输出两个整数li,ri,表示分开后第i个结点的左儿子编号和右儿子编号,如果为空请输出0,两个整数间以一个空格相间。
5 2 0 0 4 3 1 2 5 4 1 0 0 2 0 0 1
0 0 3 0 0 4 5 0 0 0
这只是其中一个可能的答案。
任何合法的方案都可以被接受。
// 没有过全部测试用例(怀疑是用例问题) 仅通过46.67% #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct TreeNode { int id, weight; struct TreeNode *left, *right; } TreeNode, *PTreeNode; typedef struct { struct TreeNode* t1; // < struct TreeNode* t2; // >= } Result; PTreeNode buildTree(int (*data)[3], int index) { if (!index) return NULL; PTreeNode root = (PTreeNode) malloc(sizeof(TreeNode)); if (!root) return NULL; root->id = index; root->weight = *(*(data + index) + 2); root->left = buildTree(data, **(data + index)); root->right = buildTree(data, *(*(data + index) + 1)); return root; } Result split(PTreeNode root, int target) { if (!root) return (Result) { .t1 = NULL, .t2 = NULL }; Result res; if (root->weight >= target) { res = split(root->left, target); root->left = res.t2; res.t2 = root; } else { res = split(root->right, target); root->right = res.t1; res.t1 = root; } return res; } void output(PTreeNode node) { printf("{%d %d}, ", (*node).id, (*node).weight); } void create_mapping(PTreeNode root, PTreeNode* repos) { if (!root) return; *(repos + root->id) = root; create_mapping(root->left, repos); create_mapping(root->right, repos); } // debug helper function void preorder(PTreeNode root, void (*visit) (PTreeNode)) { if (!root) return; visit(root); preorder(root->left, visit); preorder(root->right, visit); } int main(void) { int n, v; scanf("%d %d", &n, &v); int data[n + 1][3], has_parent[n + 1]; memset(has_parent, 0x0000, sizeof has_parent); int i, l, r, w; for (i = 1; i <= n; ++i) { scanf("%d %d %d", &l, &r, &w); data[i][0] = l; data[i][1] = r; data[i][2] = w; if (l != 0) has_parent[l] = 1; if (r != 0) has_parent[r] = 1; } int root_idx = 1; while (has_parent[root_idx]) ++root_idx; PTreeNode root = buildTree(data, root_idx); PTreeNode repos[n + 1]; create_mapping(root, repos); split(root, v); PTreeNode node; for (i = 1; i <= n; ++i) { node = *(repos + i); l = node->left ? node->left->id : 0; r = node->right ? node->right->id : 0; printf("%d %d\n", l, r); } return 0; }
#include <iostream> #include <unordered_map> using namespace std; struct TreeNode { int li; int ri; int vi; }; unordered_map<int, TreeNode*> littleTree; unordered_map<int, TreeNode*> bigTree; int littleTreeRootId = 0; int bigTreeRootId = 0; int insertToLittleTree(int vi, int idx, int curId) { if (idx == 0) { if(littleTree.empty()) { littleTreeRootId = curId; } littleTree[curId] = new TreeNode{0, 0, vi}; return curId; } if (vi <= littleTree[idx]->vi) { littleTree[idx]->li = insertToLittleTree(vi, littleTree[idx]->li, curId); return idx; } littleTree[idx]->ri = insertToLittleTree(vi, littleTree[idx]->ri, curId); return idx; } int insertToBigTree(int vi, int idx, int curId) { if (idx == 0) { if(bigTree.empty()) { bigTreeRootId = curId; } bigTree[curId] = new TreeNode{0, 0, vi}; return curId; } if (vi <= bigTree[idx]->vi) { bigTree[idx]->li = insertToBigTree(vi, bigTree[idx]->li, curId); return idx; } bigTree[idx]->ri = insertToBigTree(vi, bigTree[idx]->ri, curId); return idx; } void insertTreeNode(int v, int vi, int idx) { if (vi <= v) { insertToLittleTree(vi, littleTreeRootId, idx); return; } insertToBigTree(vi, bigTreeRootId, idx); } void printTree(int num) { for(int i = 1; i <= num; ++i) { if(littleTree.count(i)) { cout <<littleTree[i]->li << " " <<littleTree[i]->ri<<'\n'; } else { cout <<bigTree[i]->li << " "<<bigTree[i]->ri<<'\n'; } } } int main() { int n, v; while (cin >> n >> v) { // 注意 while 处理多个 case int li, ri, vi; littleTree.clear(); bigTree.clear(); littleTreeRootId = 0; bigTreeRootId = 0; for (int i = 1; i <= n; ++i) { cin >> li >> ri >> vi; insertTreeNode(v, vi, i); } printTree(n); } }
# 思路:仅通过46.67% # 将小于给定值的节点的权值和索引放在一个列表内,同理将不小于给定值的节点放在另一个列表内 # 将两个列表按权值排序 # 两棵树全部只有左子树,即最小权值的做叶节点,然后按权值升序给节点找到其父节点 lineone = input().split() n, v = int(lineone[0]), int(lineone[1]) nodes = [] res = [] for i in range(n): linen = input().split() nodes.append([int(linen[0]), int(linen[1]), int(linen[2])]) res.append([]) greater = [] smaller = [] for ind in range(1,len(nodes)+1): if nodes[ind-1][-1] < v: smaller.append([nodes[ind-1][-1], ind]) else: greater.append([nodes[ind-1][-1], ind]) greater = sorted(greater, key=lambda x: x[0]) smaller = sorted(smaller, key=lambda x: x[0]) temp = 0 for i in range(len(greater)): ind = greater[i][1]-1 if i == 0: res[ind].append(0) res[ind].append(0) temp = ind + 1 else: res[ind].append(temp) res[ind].append(0) temp = ind + 1 temp = 0 for i in range(len(smaller)): ind = smaller[i][1]-1 if i == 0: res[ind].append(0) res[ind].append(0) temp = ind + 1 else: res[ind].append(temp) res[ind].append(0) temp = ind + 1 for i in range(len(res)): print(str(res[i][0]) + " " + str(res[i][1]))