PAT-Advanced BinaryTree

2020-04-09
Abstract：都挺简单，就是读取输入就占了一大半内容

1115 Counting Nodes in a BST (30分)

image-20200409191044003

解法一

觉得应该有更快更方便的方法，但是暂时没想到

#include<iostream>
#include<algorithm>

struct TreeNode {
	int val;
	TreeNode* left, * right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
} * bst;

int num, val, n1 = 0, n2 = 0;

void insert(TreeNode* curr, TreeNode* node) {
	if (!curr) return;
	if (node->val <= curr->val) {
		if (!curr->left) curr->left = node;
		else insert(curr->left, node);
	}
	else {
		if (!curr->right) curr->right = node;
		else insert(curr->right, node);
	}
}

void parseInput() {
	std::cin >> num;
	std::cin >> val;
	bst = new TreeNode(val);
	for (int i = 1; i < num; i++) {
		std::cin >> val;
		TreeNode* node = new TreeNode(val);
		insert(bst, node);
	}
}

int maxDepth(TreeNode* root, int depth, int maxdepth) { // 获取最大深度，才能知道哪层是最后一层和倒数第二层
	if (!root) return maxdepth;
	int left = maxDepth(root->left, depth+1, maxdepth);
	int right = maxDepth(root->right, depth+1, maxdepth);
	int maxchild = std::max(left, right);
	maxdepth = std::max(maxchild, depth);
	return maxdepth;
}
	
void countLastTwoRow(TreeNode* root, int depth, int maxdepth) { // 计数
	if (root == NULL) return;
	countLastTwoRow(root->left, depth+1, maxdepth);
	if (depth == maxdepth) n1++;
	if (depth == maxdepth - 1) n2++;
	countLastTwoRow(root->right, depth+1, maxdepth);
}

int main() {
	parseInput();
	int maxdepth = maxDepth(bst, 0, 0);
	// std::cout << maxdepth << std::endl;
	countLastTwoRow(bst, 0, maxdepth);
	std::cout << n1 << " + " << n2 << " = " << n1 + n2;
}

1020 Tree Traversals (25分)

image-20200410204712369

解法一：常规方法

先由中后序遍历生成树，再层序遍历

#include<iostream>
#include<vector>
#include<queue>

struct TreeNode {
	int val;
	TreeNode* left, * right;
	TreeNode(int x) :val(x), left(NULL), right(NULL) {}
} *root;

int num;
std::vector<int> postorder, inorder;

void parseInput() {
	std::cin >> num;
	postorder = std::vector<int>(num);
	inorder = std::vector<int>(num);
	for (int i = 0; i < num; i++) std::cin >> postorder[i];
	for (int i = 0; i < num; i++) std::cin >> inorder[i];
}

TreeNode* genBinaryTree(int p_lo, int p_hi, int i_lo, int i_hi) {
	if (p_lo > p_hi || i_lo > i_hi) return NULL;    //越界判定 & 递归结束
	int left_size = 0;
	for (int i = i_lo; i <= i_hi; i++)              //在inorder中找到root并算出left_size
		if (inorder[i] == postorder[p_hi]) left_size = i - i_lo;

	TreeNode* root = new TreeNode(postorder[p_hi]); //依据已有关系，构造根节点和左右子树
	root->left = genBinaryTree(p_lo, p_lo + left_size - 1, i_lo, i_lo + left_size - 1);
	root->right = genBinaryTree(p_lo + left_size, p_hi - 1, i_lo + left_size + 1, i_hi);
	return root;
}

void levelOrder(TreeNode* root) {
	if (root == NULL) return;
	std::queue<TreeNode> q = std::queue<TreeNode>();
	q.push(*root);
	while (!q.empty()) {
		TreeNode curr = q.front(); q.pop();
		if (curr.left != NULL) q.push(*curr.left);
		if (curr.right != NULL) q.push(*curr.right);
		if (!q.empty()) std::cout << curr.val << " ";
		else std::cout << curr.val; // 左右子树都为空且队列为空，说明是最后一个节点了
	}
}

int main() {
	parseInput();
	root = genBinaryTree(0, num - 1, 0, num - 1);
	levelOrder(root);
}

解法二：静态树

不构造树，而是用一个超大数组来对应树的节点，也就是树的顺序存储，当然，是稀疏的

#include<iostream>
#include<vector>

int num;
std::vector<int> postorder, inorder, levelorder;

void parseInput() {
	std::cin >> num;
	postorder = std::vector<int>(num);
	inorder = std::vector<int>(num);
	levelorder = std::vector<int>(100000, -1);
	for (int i = 0; i < num; i++) std::cin >> postorder[i];
	for (int i = 0; i < num; i++) std::cin >> inorder[i];
}

void levelOrder(int root, int lo, int hi, int idx) {
	if (lo > hi) return;
	int i = lo;
	for (i; i < hi && inorder[i] != postorder[root]; i++); // 定位到root
	levelorder[idx] = postorder[root];
	levelOrder(root - 1 - hi + i, lo, i - 1, 2 * idx + 1); // 2*idx+1是假设是满二叉树的清况
	levelOrder(root - 1, i + 1, hi, 2 * idx + 2);
}

int main() {
	parseInput();
	levelOrder(num - 1, 0, num - 1, 0);
	for (int i = 0, idx = 0; i < levelorder.size(); i++) {
		if (levelorder[i] != -1 && idx != num - 1) { std::cout << levelorder[i] << " "; idx++; }
		else if (levelorder[i] != -1) { std::cout << levelorder[i]; break; }
	}
}

1043 Is It a Binary Search Tree (25分)

image-20200411002910741

image-20200411002922767

解法一

  • 先判断出是升序树还是降序树，然后生成对应的BST
  • inorder判断是否有序
  • 最后根据是否有序输出对应的结果
#include<iostream>
#include<vector>
struct TreeNode {
	int val;
	TreeNode* left, * right;
	TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};

int num, mode = 0;
std::vector<int> preorder, inorder, postorder;

void parseInput() {
	std::cin >> num;
	preorder = std::vector<int>(num);
	for (int i = 0; i < num; i++)std::cin >> preorder[i];
	int i = 1; for (i; i < num && preorder[0] == preorder[i]; i++);
	mode = preorder[0] < preorder[i] ? 1 : 0; // 找到第一个与根不等的节点进行比较，判断升序还是降序
}

bool compare(int a, int b, int mode) {
	return mode == 1 ? a >= b : a <= b;
}

TreeNode* genBST(int lo, int hi) {
	if (lo > hi)return NULL;
	int right = lo;
	for (right; right <= hi && compare(preorder[right], preorder[lo], mode); right++); // 定位到右子树
	TreeNode* root = new TreeNode(preorder[lo]);
	root->left = genBST(lo + 1, right - 1);
	root->right = genBST(right, hi);
	return root;
}

void genInOrder(TreeNode* root) {
	if (root == NULL) return;
	genInOrder(root->left);
	inorder.push_back(root->val);
	genInOrder(root->right);
}

void genPostOrder(TreeNode* root) {
	if (root == NULL) return;
	genPostOrder(root->left);
	genPostOrder(root->right);
	postorder.push_back(root->val);
}

int main() {
	parseInput();
	TreeNode* root = genBST(0, num - 1);
	genInOrder(root);
	bool res = true; // 
	for (int i = 1; i < num; i++) if (!compare(inorder[i - 1], inorder[i], mode)) res = false;
	//for (int i : inorder)std::cout << i << " ";
	if (res == false) std::cout << "NO";
	else {
		genPostOrder(root);
		std::cout << "YES" << std::endl;
		for (int i = 0; i < num; i++) {
			if (i == num - 1)std::cout << postorder[i];
			else std::cout << postorder[i] << " ";
		}
	}
}

1099 Build A Binary Search Tree (30分)

image-20200411012519511

image-20200411012534482

解法一：std::sort()

我知道这很无耻，但是爽啊！

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

struct TreeNode {
	int val, left, right;
} tree[101];

int num, left, right, index = 0;
std::vector<int> inorder;

void parseInput() {
	std::cin >> num;
	inorder = std::vector<int>(num);
	for (int i = 0; i < num; i++) {
		std::cin >> left >> right;
		tree[i] = { -1,left,right };
	}
	for (int i = 0; i < num; i++) std::cin >> inorder[i];
	std::sort(inorder.begin(), inorder.end());
}

void levelOrder(int root) {
	if (root == -1) return;
	std::queue<int> q = std::queue<int>();
	q.push(root);
	while (!q.empty()) {
		int curr = q.front(); q.pop();
		if (tree[curr].left != -1) q.push(tree[curr].left);
		if (tree[curr].right != -1) q.push(tree[curr].right);
		if (q.empty())std::cout << tree[curr].val;
		else std::cout << tree[curr].val << " ";
	}
}

void fillBST(int root) {
	if (root == -1) return;
	fillBST(tree[root].left);
	tree[root].val = inorder[index++];
	fillBST(tree[root].right);
}

int main() {
	parseInput();
	fillBST(0);
	levelOrder(0);
}

简化版

1138 Postorder Traversal (25分)

image-20200411153127602

解法一

这题看起来很简单，就是个穷人版的生成后序遍历，但是实际上时间卡得非常死

  • 直接使用 std::cin & std::cout
  • 递归没有提前结束
  • root没有缓存而是每次都线性遍历子树部分

以上三者任意一者均可以使部分测试点超时

#include<iostream>
#include<vector>
#include<unordered_map>

int num, ans = 0;
std::vector<int> preorder, inorder;
std::unordered_map<int, int> map = std::unordered_map<int,int>();

void parseInput() {
	std::ios::sync_with_stdio(false); std::cin.tie(0);
	std::cin >> num;
	preorder = std::vector<int>(num);
	inorder = std::vector<int>(num);
	for (int i = 0; i < num; i++)std::cin >> preorder[i];
	for (int i = 0; i < num; i++) {
		std::cin >> inorder[i];
		map[inorder[i]] = i;                                // 将inorder的值索引缓存
	}
}

void genPostOrder(int p_lo, int p_hi, int i_lo, int i_hi) {
	if (p_lo > p_hi || i_lo > i_hi || ans != 0) return;
	int root = preorder[p_lo]; int left = map[root] - i_lo; // 直接hash取得index计算左区间
	genPostOrder(p_lo + 1, p_lo + left, i_lo, i_lo + left - 1);
	genPostOrder(p_lo + left + 1, p_hi, i_lo + left + 1, i_hi);
	if (ans == 0) { std::cout << root; ans = root; }
}

int main() {
	parseInput();
	genPostOrder(0, num - 1, 0, num - 1);
}

1127 ZigZagging on a Tree (30分)

image-20200417230626586

解法一：BFS

中序后序建树就不说了，基本功

类似于标准的level order traversal， 中间插入NULL来区分层级，每过一层，转换一次输出顺序

#include<iostream>
#include<vector>
#include<queue>

struct TreeNode {
	int val;
	TreeNode* left, * right;
	TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};

int num;
std::vector<int> inorder, postorder, zigzag;
bool isleft = false;

void parseInput() {
	std::cin >> num;
	inorder = std::vector<int>(num);
	postorder = std::vector<int>(num);
	for (int i = 0; i < num; i++)
		std::cin >> inorder[i];
	for (int i = 0; i < num; i++)
		std::cin >> postorder[i];
}

TreeNode* genBinaryTree(int i_lo, int i_hi, int p_lo, int p_hi) {
	if (i_lo > i_hi || p_lo > p_hi) return NULL;

	int r = postorder[p_hi], left = 0;
	for (int i = i_lo; i <= i_hi; i++)
		if (inorder[i] == r) left = i - i_lo;

	TreeNode* root = new TreeNode(r);
	root->left = genBinaryTree(i_lo, i_lo + left - 1, p_lo, p_lo + left - 1);
	root->right = genBinaryTree(i_lo + left + 1, i_hi, p_lo + left, p_hi - 1);
	return root;
}

void zigZag(TreeNode* root) {
	std::deque<TreeNode*> q;
	q.push_back(root);
	q.push_back(NULL);
	std::vector<std::deque<TreeNode*>> res;
	std::deque<TreeNode*> list;
	while (!q.empty()) {
		TreeNode* curr = q.front(); q.pop_front();
		if (curr) {

			if (isleft)
				list.push_back(curr);
			else
				list.push_front(curr);
			if (curr->left) q.push_back(curr->left);
			if (curr->right) q.push_back(curr->right);
		}
		else {
			res.push_back(list);
			list.clear();
			if (!q.empty())
				q.push_back(NULL);
			isleft = !isleft;
		}
	}
	for (int i = 0; i < res.size(); i++) {
		for (int j = 0; j < res[i].size(); j++) {
			if (i == res.size() - 1 && j == res[i].size() - 1)
				std::cout << res[i][j]->val;
			else
				std::cout << res[i][j]->val << " ";
		}
	}

}

int main() {
	parseInput();
	TreeNode* root = genBinaryTree(0, num - 1, 0, num - 1);
	zigZag(root);
}

1004 Counting Leaves (30分)

image-20200419164928677

解法一

虽然不是二叉树，但还是放这好了/懒，作为一道30分的题有点太简单了

#include<iostream>
#include<vector>

int num, m, id, k, child_id;
std::vector<int> childs, res;

struct TreeNode {
	std::vector<int> childs;
} node[100];

void parseInput() {
	std::cin >> num >> m;
	for (int i = 0; i < m; i++) {
		std::cin >> id >> k;
		for (int i = 0; i < k; i++) {
			std::cin >> child_id;
			childs.push_back(child_id);
		}
		node[id] = { childs };
		childs.clear();
	}
}

void tranversal(int id, int depth) {
	while (depth >= res.size()) res.push_back(0);
	if (node[id].childs.empty()) {
		res[depth]++;
		return;
	}
	for (int i : node[id].childs) tranversal(i, depth + 1);
}

int main() {
	parseInput();
	tranversal(01, 0);
	for (int i = 0; i < res.size(); i++) {
		if (i == res.size() - 1) 
			std::cout << res[i];
		else 
			std::cout << res[i] << " ";
	}
}
© 2020 Overyam - Powered by Hexo - Theme Chan