二叉树

PAT (Advanced Level) Practice 二叉树 相关题

目录

  • 《算法笔记》 重点摘要
  • 1020 Tree Traversals (25)
  • 1086 Tree Traversals Again (25)
  • 1102 Invert a Binary Tree (25)
  • 1119 Pre- and Post-order Traversals (30)
  • 1127 ZigZagging on a Tree (30)
  • 1138 Postorder Traversal (25)
  • 1151 LCA in a Binary Tree (30)
  • 附：二叉树链式实现

《算法笔记》 9.2 二叉树 重点摘要

1. 常考边界条件

  • 空树：没有结点
  • 树只有一个根节点时，它亦为叶子结点

2. 完全二叉树

  • 建立大小为 2^k 的数组，其中 k 为完全二叉树的最大高度
  • 若题目规定为完全二叉树，数组大小 n+1 即可
  • 1 号位存放根节点
  • 任一编号为 x 的结点，左孩子编号 2x，右孩子编号 2x+1
  • 判断结点是否为叶结点：2x > n
  • 判断结点是否为空：x > n

3. 二叉树静态实现 ⭐

(1) 定义
struct Node{

    typename data;

    int level;

    int lchild;

    int rchild;

} node[MAXN];
(2) 新建结点
int index = 0;

int newNode (int value){

    node[index].data = value;

    node->lchild = node->rchild = -1;

    return index++;

}
(3) 插入
void insert (int &root, int value){

    if (root == -1){

        root = newNode(value);

        return;

    }

    if (由二叉树性质应插入在左子树) insert(node[root].lchild, value);

    else insert(node[root].rchild, value);

}
(4) 创建
int create(int value[], int n){

    int root = -1;

    for (int i = 0; i < n; i++) insert(root, data[i]);

    return root;

}
(5) 查找&修改
void search (int root, int value, int newvalue){

    if (root == -1) return;

    if (node[root].data == value) node[root].data = newvalue;

    search(node[root].lchild, value, newvalue);

    search(node[root].rchild, value, newvalue);

}
(6) 先序遍历
void preorder(int root){

    if (root == -1) return;

    printf("%d\n", node[root].data);

    preorder(node[root].lchild);

    preorder(node[root].rchild);

}
(7) 中序遍历
void inorder(int root){

    if (root == -1) return;

    preorder(node[root].lchild);

    printf("%d\n", node[root].data);

    preorder(node[root].rchild);

}
(8) 后序遍历
void postorder(int root){

    if (root == -1) return;

    preorder(node[root].lchild);

    preorder(node[root].rchild);

    printf("%d\n", node[root].data);

}
(10) 层序遍历
void levelorder(int root){

    queue<int> q;

    q.push(root);

    while (!q.empty()){

        int now = q.front();

        q.pop();

        printf("%d", node[now].data);

        if (node[now].lchild != -1) q.push(node[now].lchild);

        if (node[now].rchild != -1) q.push(node[now].rchild);

    }

}
(11) 根据先序+中序重建树
int create (int preL, int preR, int inL, int inR){

    if (preL > preR) return -1;

    int root = new Node(pre[preL]);

    int k;

    for (k = inL; k <= inR; k++)

        if (in[k] == pre[preL]) break;

    int numLeft = k - inL;  // 左子树结点个数

    node[root].lchild = create(preL+1, preL+numLeft, inL, k-1);

    node[root].rchild = create(preL+numLeft+1, preR, k+1, inR);

    return root;

}

1020 Tree Traversals (25)

中序后序转先序

  • 后序的最后一个即为根节点，递归每次先取到根节点再分别递归进入左子树和右子树
  • 若要获得先序遍历，只要在递归访问到根节点时存到容器中即可
#include<iostream>

#include<vector>

using namespace std;

int post[31], in[31];

vector<int> pre;

void preorder(int post_root, int inL, int inR)

{

	if (inL > inR) return;

	pre.push_back(post[post_root]);

	int k;

	for (k = inL; k <= inR; k++)

		if (in[k] == post[post_root]) break;

	preorder(post_root-1-inR+k, inL, k-1);

	preorder(post_root-1, k+1, inR);

}

int main()

{

	int n;

	scanf("%d",&n);

	for (int i = 0; i < n; i++) scanf("%d", post+i);

	for (int i = 0; i < n; i++) scanf("%d", in+i);

	preorder(n-1, 0, n-1);

	printf("%d",pre[0]);

	for (int i = 1; i < pre.size(); i++) printf(" %d",pre[i]);

	return 0;

}

中序后序转层序

  • 要按层序遍历，不可以直接在遍历时得到最终值序列的顺序，需要进行标号排序
  • 用完全二叉树的标号，即根从 1 开始，将 根标号 index 的 2*index 传给左子树，赋给左子树的根；将 2*index+1 给右子树的根
  • 若左右子树为空，直接返回未压入新节点，相当于层序遍历结点容器中对应的序号空了出来，不影响后面按序号排序的顺序
  • 递归完成后，对层序遍历结点容器按序号排序，再按序输出结点对应值
#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

struct Node{

	int index, value;

};

bool cmp (Node a, Node b){ return a.index < b.index; }

int post[31], in[31];

vector<Node> level;

void levelorder(int post_root, int inL, int inR, int index)

{

	if (inL > inR) return;

	level.push_back({index,post[post_root]});

	int k;

	for (k = inL; k <= inR; k++)

		if (in[k] == post[post_root]) break;

	levelorder(post_root-1-inR+k, inL, k-1, 2 * index);

	levelorder(post_root-1, k+1, inR, 2 * index + 1);

}

int main()

{

	int n;

	scanf("%d",&n);

	for (int i = 0; i < n; i++) scanf("%d", post+i);

	for (int i = 0; i < n; i++) scanf("%d", in+i);

	levelorder(n-1, 0, n-1, 1);

	sort(level.begin(),level.end(),cmp);

	printf("%d",level[0].value);

	for (int i = 1; i < level.size(); i++) printf(" %d",level[i].value);

	return 0;

}

建树方法

#include<iostream>

#include<queue>

#include<vector>

using namespace std;

struct Node{

	int data, lchild, rchild;

} node[31];

int index = 0;

int post[31], in[31];

int newNode(int value)

{

	node[index].data = value;

	node[index].lchild = node[index].rchild = -1;

	return index++;

}

int build(int postL, int postR, int inL, int inR)

{

	if (postL > postR) return -1;

	int root = newNode(post[postR]);

	int k;

	for (k = inL; k <= inR; k++)

		if (in[k] == post[postR]) break;

	int leftnum = k - inL;

	node[root].lchild = build(postL, postL+leftnum-1, inL, k-1);

	node[root].rchild = build(postL+leftnum, postR-1, k+1, inR);

	return root;

}

void levelorder(int root){

	queue<int> q;

	q.push(root);

	vector<int> result;

	while(!q.empty()){

		int now = q.front();

		q.pop();

		result.push_back(now);

		if (node[now].lchild != -1) q.push(node[now].lchild);

		if (node[now].rchild != -1) q.push(node[now].rchild);

	}

	printf("%d", node[result[0]].data);

	for (int i = 1; i < result.size(); i++) printf(" %d", node[result[i]].data);

}

int main()

{

	int n;

	scanf("%d",&n);

	for (int i = 0; i < n; i++) scanf("%d", post+i);

	for (int i = 0; i < n; i++) scanf("%d", in+i);

	int root = build(0, n-1, 0, n-1);

	levelorder(root);

	return 0;

}

1086 Tree Traversals Again (25)

题目思路

  • 栈实现的是二叉树的中序遍历（左根右）
  • ⭐每次 push 值的顺序是二叉树的前序遍历（根左右）
  • 前序中序转后序
#include<iostream>

#include<vector>

#include<stack>

using namespace std;

vector<int> in, pre, post;

void postorder(int preroot, int inL, int inR){

	if (inL > inR) return;

	int k;

	for (k = inL; k <= inR; k++)

		if (in[k] == pre[preroot]) break;

	postorder(preroot+1, inL, k-1);

	postorder(preroot+k-inL+1, k+1, inR);

	post.push_back(pre[preroot]);

}

int main()

{

	int n, num;

	scanf("%d", &n);

	string op;

	stack<int> s;

	for (int i = 0; i < 2 * n; i++){

		cin >> op;

		if (op.length() > 3){

			scanf("%d", &num);

			pre.push_back(num);

			s.push(num);

		} else{

			in.push_back(s.top());

			s.pop();

		}

	}

	postorder(0, 0, n-1);

	for (int i = 0; i < n; i++)

		printf("%d%c", post[i], i == n - 1 ? '\n' : ' ');

	return 0;

}

1102 Invert a Binary Tree (25)

建树 + 层序遍历 + 中序遍历

  • 只需要树的结构，没有数据，用 vector 存储左右孩子下标即可，遍历输出根的下标即可
  • invert tree 即将所有结点左右孩子对调，输入并存储时直接对调存储即可
  • 在左右孩子中没有出现过的下标即为根的下标，用 bool 数组记录是否出现过
#include<iostream>

#include<vector>

#include<queue>

using namespace std;

vector<pair<int,int>> node;

vector<int> level, in;

void levelorder(int root)

{

	queue<int> q;

	q.push(root);

	while (!q.empty()){

		int now = q.front();

		level.push_back(now);

		q.pop();

		if (node[now].first != -1) q.push(node[now].first);

		if (node[now].second != -1) q.push(node[now].second);

	}

}

void inorder(int root)

{

	if (root == -1) return;

	inorder(node[root].first);

	in.push_back(root);

	inorder(node[root].second);

}

int main()

{

	int n;

	scanf("%d",&n);

	char a, b;

	getchar();

	bool appear[n] = {false};

	for (int i = 0; i < n; i++){

		scanf("%c %c", &a, &b);

		getchar();

		if (a != '-') appear[a-'0'] = true;

		if (b != '-') appear[b-'0'] = true;

		a = a == '-' ? -1 : a-'0';

		b = b == '-' ? -1 : b-'0';

		node.push_back({b,a});

	}

	int root = 0;

	while (appear[root]) root++;

	levelorder(root);

	printf("%d", level[0]);

	for (int i = 1; i < level.size(); i++) printf(" %d", level[i]);

	inorder(root);

	printf("\n%d", in[0]);

	for (int i = 1; i < in.size(); i++) printf(" %d", in[i]);

	return 0;

}

1119 Pre- and Post-order Traversals (30)

题意理解

  • 二叉树的前序和后序无法唯一确定一颗二叉树，因为一个结点可能是根的左孩子也有可能是根的右孩子，题目要求不唯一时生成其中一个可行解即可
  • 前序遍历：根左右；后序遍历：左右根；从遍历顺序可知前序遍历时根节点后面面紧跟着一个子节点；同理，后序遍历的根节点前面紧贴着他的一个子节点
  • 这两个节点比较，若不同，说明根的左右节点确定，若相同，此结点既可能是左节点也可能是右结点，建树不唯一

题目思路

  • 用变量 unique 标记是否唯一，默认唯一置 true，比较发现不唯一时再标记为 false
  • 递归时需要知道树的表示范围 =》 四个变量：前序左 preL, 前序右 preR, 后序左 postL, 后序右 postR
  • preL 与 postR 对应结点相同，为根节点
  • 在前序序列中找后序右前一个子结点 (pre[k] == post[postR-1])，默认其为右子树结点，则其在先序序列中前面的结点即为左子树节点
  • 处理左子树
    • 左子树大小为 numL = k - preL - 1
    • 若左子树不为空，则左右子树确定，递归进入左子树
    • 若左子树为空，说明 post[postR-1] 这一点可能在左也可能在右，应置 unique = false
  • 左子树处理完毕后将根节点 post[postR] 压入中序序列
  • 再递归进入右子树进行处理
  • 当 preL == preR 时说明子树仅有一个结点，则不必进行复杂处理，直接压入中序序列即可
  • 注意：格式错误时要检查所有数据输出完成后是否需要输出换行
#include<iostream>

#include<vector>

using namespace std;

vector<int> pre, post, in;

bool unique = true;

void inorder(int preL, int preR, int postL, int postR)

{

	if (preL == preR){

		in.push_back(pre[preL]);

		return;

	}

	int k;

	for (k = preL + 1; k <= preR && pre[k] != post[postR-1]; k++);

	int numL = k - preL - 1;

	if (numL > 0) inorder(preL+1, k-1, postL, postL+numL-1);

	else unique = false;

	in.push_back(post[postR]);

	inorder(k, preR, postL+numL, postR-1);

}

int main()

{

	int n;

	scanf("%d", &n);

	pre.resize(n);

	post.resize(n);

	for (int i = 0; i < n; i++) scanf("%d", &pre[i]);

	for (int i = 0; i < n; i++) scanf("%d", &post[i]);

	inorder(0, n-1, 0, n-1);

	printf("%s\n", unique ? "Yes" : "No");

	for (int i = 0; i < in.size(); i++) printf("%d%c", in[i], i+1 == in.size() ? '\n' : ' ');

	return 0;

}

1127 ZigZagging on a Tree (30)

题目思路

  • 不需要建树，用深搜思想递归，传入参数 level
  • 用 vector 数组保存每一层从左到右的结点内容
  • 每次递归根据传入 level 将所在结点压入对应层容器中
  • 再递归分别进入左右子树，找左右子树方法与中后序转先序类似
  • 递归结束后得到保存了每层内容的 vector 数组
  • 先输出根，因为根结点一层仅有一个结点
  • 从下一层开始，奇数层从左到右输出，偶数层从右到左输出
#include<iostream>

#include<vector>

using namespace std;

vector<int> in, post, leveldata[31];

void leveltrave(int root, int inL, int inR, int level){

	if (inL > inR) return;

	leveldata[level].push_back(post[root]);

	int k;

	for (k = inL; k <= inR; k++)

		if (in[k] == post[root]) break;

	leveltrave(root-(inR-k)-1, inL, k-1, level+1);

	leveltrave(root-1, k+1, inR, level+1);

}

int main()

{

	int n;

	scanf("%d", &n);

	in.resize(n);

	for (int i = 0; i < n; i++) scanf("%d", &in[i]);

	post.resize(n);

	for (int i = 0; i < n; i++) scanf("%d", &post[i]);

	leveltrave(n-1, 0, n-1, 0);

	printf("%d", leveldata[0][0]);

	for (int i = 1; i < 31; i++){

		if (i % 2)

			for (int j = 0; j < leveldata[i].size(); j++)

				printf(" %d",leveldata[i][j]);

		else

			for (int j = leveldata[i].size(); j > 0; j--)

				printf(" %d",leveldata[i][j-1]);

	}

	return 0;

}

1138 Postorder Traversal (25)

前序中序转后序

#include<iostream>

#include<vector>

using namespace std;

vector<int> pre, in, post;

void postorder(int pre_root, int inL, int inR)

{

	if (inL > inR) return;

	int k;

	for (k = inL; k <= inR; k++)

		if (pre[pre_root] == in[k]) break;

	postorder(pre_root+1, inL, k-1);

	postorder(pre_root+1+k-inL, k+1, inR);

	post.push_back(pre[pre_root]);

}

int main()

{

	int n, value;

	scanf("%d",&n);

	for (int i = 0; i < n; i++){

		scanf("%d", &value);

		pre.push_back(value);

	}

	for (int i = 0; i < n; i++){

		scanf("%d", &value);

		in.push_back(value);

	}

	postorder(0, 0, n-1);

	printf("%d", post[0]);

	return 0;

}

时间优化

  • 由于只要知道后序第一个即可，可设置标记变量
  • 还未输出过置为 false，第一个输出时改为 true
  • 进入递归时检查变量，若为true可不必再继续递归，可减少运行时间
#include<iostream>

#include<vector>

using namespace std;

vector<int> pre, in;

bool flag = false;

void postorder(int pre_root, int inL, int inR)

{

	if (inL > inR || flag) return;

	int k;

	for (k = inL; k <= inR; k++)

		if (pre[pre_root] == in[k]) break;

	postorder(pre_root+1, inL, k-1);

	postorder(pre_root+1+k-inL, k+1, inR);

	if (!flag){

		flag = true;

		printf("%d",pre[pre_root]);

	}

}

int main()

{

	int n, value;

	scanf("%d",&n);

	for (int i = 0; i < n; i++){

		scanf("%d", &value);

		pre.push_back(value);

	}

	for (int i = 0; i < n; i++){

		scanf("%d", &value);

		in.push_back(value);

	}

	postorder(0, 0, n-1);

	return 0;

}

1151 LCA in a Binary Tree (30)

题目思路

  • 已知某个树的根结点
  • 若 u 和 v 在根结点的左边，则 u 和 v 的最近公共祖先在当前子树根结点的左子树寻找
  • 若 u 和 v 在当前子树根结点的右边，则 u 和 v 的最近公共祖先就在当前子树的右子树寻找
  • 若 u 和 v 在当前子树根结点的两边，在当前子树的根结点就是 u 和 v 的最近公共祖先
  • 若 u 或 v 等于根节点，则其为另一个点的祖先
  • 每次递归都要重新定位当前根节点与两个待查结点的左右子树关系，其实中序遍历已经给出了这个关系
  • 将结点内容和中序遍历的序号构成映射，每次递归直接取出序号进行比较而不是扫描序列
#include<iostream>

#include<vector>

#include<unordered_map>

using namespace std;

vector<int> pre, in;

unordered_map<int,int> inidx;

int u, v;

void LCA(int root, int inL, int inR){

	if (inL > inR) return;

	int k = inidx[pre[root]], uin = inidx[u], vin = inidx[v];

	if (k == uin) printf("%d is an ancestor of %d.\n", u, v);

	else if (k == vin) printf("%d is an ancestor of %d.\n", v, u);

	else if (uin < k && vin < k) LCA(root+1, inL, k-1);

	else if (uin > k && vin > k) LCA(root+k-inL+1, k+1, inR);

	else printf("LCA of %d and %d is %d.\n", u, v, pre[root]);

}

int main()

{

	int m, n;

	scanf("%d%d", &m, &n);

	in.resize(n);

	for (int i = 0; i < n; i++){

		scanf("%d", &in[i]);

		inidx[in[i]] = i;

	}

	pre.resize(n);

	for (int i = 0; i < n; i++) scanf("%d", &pre[i]);

	for (int i = 0; i < m; i++){

		scanf("%d%d", &u, &v);

		if (inidx.find(u) == inidx.end() && inidx.find(v) == inidx.end())

			printf("ERROR: %d and %d are not found.\n", u, v);

		else if (inidx.find(u) == inidx.end()) printf("ERROR: %d is not found.\n", u);

		else if (inidx.find(v) == inidx.end()) printf("ERROR: %d is not found.\n", v);

		else LCA(0, 0, n-1);

	}

	return 0;

}

附：

二叉树链式实现

(1) 定义
struct Node{

    typename data;

    int level

    Node* lchild;

    Node* rchild;

}
(2) 新建结点
Node* newNode (int value){

    Node* node = new Node;

    node->data = value;

    node->lchild = node->rchild = NULL;

    return node;

}
(3) 插入
void insert (Node* &root, int value){

    if (root == NULL){

        root = newNode(value);

        return;

    }

    if (由二叉树性质应插入在左子树) insert(root->lchild, value);

    else insert(root->rchild, value);

}
(4) 创建
Node* create(int value[], int n){

    node* root = NULL;

    for (int i = 0; i < n; i++) insert(root, data[i]);

    return root;

}
(5) 查找&修改
void search (Node* root, int value, int newvalue){

    if (root == NULL) return;

    if (root->data == value) root->data = newvalue;

    search(root->lchild, value, newvalue);

    search(root->rchild, value, newvalue);

}
(6) 先序遍历
void preorder(Node* root){

    if (root == NULL) return;

    printf("%d\n", root->data);

    preorder(root->lchild);

    preorder(root->rchild);

}
(7) 中序遍历
void inorder(Node* root){

    if (root == NULL) return;

    preorder(root->lchild);

    printf("%d\n", root->data);

    preorder(root->rchild);

}
(8) 后序遍历
void postorder(Node* root){

    if (root == NULL) return;

    preorder(root->lchild);

    preorder(root->rchild);

    printf("%d\n", root->data);

}
(10) 层序遍历
void levelorder(Node* root){

    queue<Node*> q;

    root->level = 1;

    q.push(root);

    while (!q.empty()){

        Node* now = q.front();

        q.pop();

        printf("%d", now->data);

        if (now->lchild != NULL){

            now->lchild->level = now->level + 1;

            q.push(now->lchild);

        }

        if (now->rchild != NULL){

            now->rchild->level = now->level + 1;

            q.push(now->rchild);

        }

    }

}
(11) 根据先序+中序重建树
Node* create (int preL, int preR, int inL, int inR){

    if (preL > preR) return NULL;

    Node* root = new Node;

    root->data = pre[preL];

    int k;

    for (k = inL; k <= inR; k++)

        if (in[k] == pre[preL]) break;

    int numLeft = k - inL;  // 左子树结点个数

    root->lchild = create(preL+1, preL+numLeft, inL, k-1);

    root->rchild = create(preL+numLeft+1, preR, k+1, inR);

    return root;

}

最新文章

  1. CodeForces 239 Long Path
  2. MVVM架构~knockoutjs系列之扩展ajax验证~验证输入数据是否与后台数据相等
  3. [bzoj1103][POI2007]大都市meg(树状数组+dfs序)
  4. [转]Android,Yocto,Meego构建系统的区别
  5. ajax温习
  6. [CoreOS 转载] CoreOS实践指南（六）：分布式数据存储Etcd（下）
  7. 本地Git仓库与Github远程仓库同步
  8. android学习笔记45——android的数据存储和IO
  9. 黄聪：HtmlAgilityPack，C#实用的HTML解析类简介
  10. 通俗易懂的讲解iphone视图控制器的生命周期
  11. 【不积跬步，无以致千里】VIM查找替换归纳总结zz
  12. Get和Post的参数传值
  13. 高级Magento模型 EAV
  14. Core Java读书笔记之String
  15. Windows中的对象
  16. 线性规划？数学？差分约束？Good Bye 2016 C
  17. angularjs 怎么获取鼠标焦点 鼠标移入显示浮动的div提示框
  18. Django REST framework--序列化
  19. nginx配置框架问题
  20. .net 代理类(WebService代理类的详解 )

热门文章

  1. 使用python2 对服务器监控（监控内存，CPU，网卡流量等）
  2. elasticsearch配置jdk
  3. x2goserver 连接问题
  4. Visual C++ 6.0精简绿色版下载及简单使用教程
  5. Messagebox自定义计时关闭
  6. vue.js中如何使用scss
  7. [Java复习] 多线程 并发 JUC 补充
  8. Qt 获取键盘输入
  9. 阶段5 3.微服务项目【学成在线】_day18 用户授权_19-微服务之间认证-Feign 拦截器
  10. java以逗号为分割符拼接字符串的技巧