当前位置：首页 > 编程日记 > 正文

1102 Invert a Binary Tree 需再做

编程日记 2024-09-07 01:30:00

1. 题目的输入是，先给出结点总数N，然后N行给出的是值为x（0<=x<=N-1）的结点的左右结点的值，若不存在左/右结点，则值为 - 。

2. 这一题我用动态链表没有做出来，根据参考书提示改用静态链表。整体思路是，将结点的值作为静态链表(也就是数组)node的下标，结点的左右结点都设为整型，将读入的字符转化为整型，如若不存在则设为-1。设置一个布尔型的哈希，把出现过的下标记录为true。全部读完后要是有一个值从来没出现过，也就是它不是任何结点的子结点，如此找到根节点。根节点作为参数传入到后序翻转二叉树函数invertTree(int root)，层次遍历输出函数levelOrder(int root)，中序遍历输出函数inOrder(int root)。

3. 参考书上说如果翻转二叉树(即把每一个结点的左右子树互换)，得用后序遍历，这个我还没明白为什么。

4. 以下是一些小技巧

（1）在输入的时候可以用scanf("%*c%c",&c)来取代getchar()+scanf("%c",&c)

（2）输出时，由于最后一个数字后面不可以有空格，那么每输出一个就对总数进行减一，然后判断是否大于1(也就是看后面是否还有没输出的)，若是则输出一个空格。但是这里有两轮输出，总数一开始需要拷贝一个副本n0，留着第二轮输出用。

（3）不管是先序、层序还是后序，框架一样，实现细节却和动态数组时不同了，特别是特判的时候不再是地址是否等于NULL，而是值是否等于-1。

AC代码

#include<cstdio>
#include<map>
#include<set>
#include<string>
#include<cstring>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>using namespace std;const int maxn = 11;bool appear[maxn] = {false};int n,n0; struct Node{int left,right;
}node[maxn];int charToInt(char c){if(c!='-'){appear[c-'0'] = true;return c-'0';}else return -1;
}int findRoot(){for(int i=0;i<n;i++){if(!appear[i])return i;}
}void invertTree(int root){if(root==-1)return;invertTree(node[root].left);invertTree(node[root].right);swap(node[root].left,node[root].right);
}void levelOrder(int root){queue<int> que;que.push(root);while(!que.empty()){int top = que.front();printf("%d",top);que.pop();if(--n)printf(" ");if(node[top].left!=-1)que.push(node[top].left);if(node[top].right!=-1)que.push(node[top].right);}
}void inOrder(int root){if(root==-1)return;inOrder(node[root].left);printf("%d",root);if(--n0)printf(" ");inOrder(node[root].right);
} int main(){scanf("%d",&n);n0 = n;//用于中序遍历计数 char left,right;for(int i=0;i<n;i++){scanf("%*c%c %c",&left,&right);node[i].left = charToInt(left);node[i].right = charToInt(right);}int root = findRoot();invertTree(root);	levelOrder(root);printf("\n");inOrder(root);printf("\n");return 0;
}

https://www.dkcj.cn/info/17614.html

1102 Invert a Binary Tree 需再做

相关文章：

iOS安全攻防(八)Thoes的Logos简介

Algs4-1.1.13编写一段代码，打印出一个M行N列的二维数组的转置(交换行和列）

1053 Path of Equal Weight

MapXtreme 2005 学习心得在地图上创建点/线并显示标注(五)

无人驾驶——对frenet坐标的理解

1079 Total Sales of Supply Chain

在VS下用C语言连接SQLServer2008

canvas.width和canvas.style.width区别以及应用

vj p1042捕风捉影题解

1090 Highest Price in Supply Chain 需再做

有关Adobe公司的PostScript语言授权问题

INTERSECT/EXCEPT VS. IN/NOT IN

聊聊storm的stream的分流与合并

1106 Lowest Price in Supply Chain

积极拥抱.NET Core开源社区

13_文件的操作模式

Vcastr 2.2 flv 网络播放器参数设置

1094 The Largest Generation

JS魔法堂：mmDeferred源码剖析

asp vb 插入,更新,删除数据库操作。

第五次作业：四则运算之升级

妙用vector:根据第一个不等的元素比较两个序列大小的利器

四个超好用的优质资源搜索网站，海量优质资源等你发现！

sql server 2008 修改sa密码

Sql Server数据库连接Oracle数据库

普通二叉树、二叉查找树、平衡二叉树常见操作汇总

Java IO系列之字节流拷贝文件性能比较

引用提高开发水平的几项必备技术

移动磁盘由于IO设备错误，要怎样寻回文件

1043 Is It a Binary Search Tree