RobbEr's Blog

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14

比如：
         源二叉树
            8
           /  \
          6   10
         / \  / \
        5  7 9  11
        
        镜像二叉树
            8
           /  \
          10   6
         / \  / \
        11 9 7   5

原理

既然我们想获得二叉树的镜像，那么根节点的两边必然是反过来的啊。所以第一步我们交换左右子树。

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

原理

从题面可得题意为层次遍历，层次遍历的核心思想为：每次出队一个元素，就将该元素的孩子节点加入队列中，直至队列中元素个数为0时，出队的顺序就是该二叉树的层次遍历结果

给出一个二叉树

简介

1. 树是由一个集合以及在该集合上定义的一种关系构成的，集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构，在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点。

树的一些基本定义

1. 树的结点——包含数据结构及若干指向其子树的分支
2. 结点的度——结点拥有的子树
3. 终端结点（叶子）——度为0的结点
4. 非终端结点（分支结点）——度不为0的结点
5. 树的度——树内各结点的度的最大值
6. 孩子——结点的子树
7. 兄弟——同一个双亲的孩子互相之间互称兄弟
8. 祖先——从根到该结点所经分支上的所有结点
9. 层次——从根开始定义起，根为第一层，根的孩子为第二层
10. 深度——树中结点的最大层次
11. 有序树——树中结点的各子数看成从左往右是有次序的
12. 森林——互不相交的树的集合
13. 二叉树——每个结点至多只有两个子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
14. 满二叉树——一颗深度为k且有2的k次方-1个结点的二叉树
15. 完全二叉树——深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树
16. 线索二叉树 ——对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化，被线索化了的二叉树称为线索二叉树

二叉树的特点

简介

TCP协议全称为传输控制协议，顾名思义，就是要对数据的传输进行一定的控制

TCP协议

应用层

区别一、是否基于连接

TCP是面向连接的协议，而UDP是面向无连接的协议

即TCP面向连接;UDP是无连接的，即发送数据之前不需要建立连接

区别二、可靠性 和 有序性

TCP 提供交付保证，无差错，不丢失，不重复，且按序到达，也保证了消息的有序性。该消息将以从服务器端发出的同样的顺序发送到客户端，*尽管这些消息到网络的另一端时可能是无序的，TCP协议将会为你排好序。

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））

• push(x)–将元素x插入栈中
• pop()–移除栈顶元素
• top()–得到栈顶元素
• min()–得到栈中最小元素

原理

这个题可以定义两个栈，一个数据栈用来存储入栈元素，另一个辅助栈用来存储最小值

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等

原理

根据栈的压入顺序判断栈的弹出顺序，其中核心的一点是抓住弹出时是从栈顶元素开始的，换句话说弹出序列中的每一个值都是某个状态下栈中的栈顶元素。

那么我们就使用一个栈来模拟压入弹出的操作，在这个过程中来反推弹出序列的正确性

题目描述

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型

原理

先分析栈和队列的不同，一个是先入后出FILO，一个是先入先出FIFO

我们拥有两个栈，可以让其中一个栈作为队列的入口，负责插入新元素；另一个栈作为队列的出口，负责移除老的元素

简介

1. 栈是一种线性数据结构
2. 栈的特征是数据的插入和删除只能通过一端来实现，这一端称为“栈顶”，相应的另一端称为“栈底”

特点

1. 栈中的数据元素遵守”先进后出“(First In Last Out)的原则，简称FILO结构
2. 限定只能在栈顶进行插入和删除操作

队列的相关概念