python深度遍历
一、什么是深度优先遍历
深度优先遍历算法是经典的图论算法。从某个节点v出发开始进行搜索。不断搜索直到该节点所有的边都被遍历完，当节点v所有的边都被遍历完以后，深度优先遍历算法则需要回溯到v以前驱节点来继续搜索这个节点。
注意：深度优先遍历问题一定要按照规则尝试所有的可能才行。
二、二叉树
2.二叉树类型
二叉树类型：空二叉树、满二叉树、完全二叉树、完美二叉树、平衡二叉树。
空二叉树：有零个节点
完美二叉树：每一层节点都是满的二叉树（如1中举例的图）
满二叉树：每一个节点都有零个或者两个子节点
完全二叉树：出最后一层外，每一层节点都是满的，并且最后一层节点全部从左排列
平衡二叉树：每个节点的两个子树的深度相差不超过1.
注：国内对完美二叉树和满二叉树定义相同
3.二叉树相关术语
术语 解释
度 节点的度为节点的子树个数
叶子节点 度为零的节点
分支节点 度不为零的节点
孩子节点 节点下的两个子节点
双亲节点 节点上一层的源节点
兄弟节点 拥有同一双亲节点的节点
根 二叉树的源头节点
深度 二叉树中节点的层的数量
DLR（先序）：
LDR（中序）：
LRD(后序）：
注意：L代表左子树R代表右子树；D代表根
6.深度优先遍历和广度优先遍历
深度优先遍历：前序、中序和后序都是深度优先遍历
从根节点出发直奔最远节点，
广度优先遍历：首先访问举例根节点最近的节点，按层次递进，以广度优先遍历上图的顺序为：1-2-3-4-5-6-7
三、面试题+励志
企鹅运维面试题：
1.二叉树遍历顺序：看上文
2.用你熟悉的语言说说怎么创建二叉树？ python看上文
㈡ python list方法总结+深浅拷贝+二叉树的深度遍历
浅拷贝：在Python中，浅拷贝是指创建一个新对象，该对象包含原始对象中的所有引用元素。这意
味着，如果原始对象包含其他对象（如列表或字典），则新对象将引用这些内部对象。更改新对象中引用的元素将影响原始对象。
深拷贝：与此相反，深拷贝不仅创建新对象，还会递归地复制原始对象中的所有子对象。这意味着新对象和原始对象之间没有任何关联，因此对新对象的修改不会影响原始对象。
Python提供``模块的`deep()`函数来实现深拷贝。请注意，对于元组，使用`tuple()`或切片操作符`:`并不会创建一份浅拷贝，反而会返回指向相同元组的引用。
下面是一个浅拷贝的示例：
首先，初始化包含列表和元组的列表`list1`。然后，对`list1`执行浅拷贝并赋予`list2`。浅拷贝后，`list2`和`list1`共享相同列表和元组对象。
接下来，执行对`list1`的操作。`list1.append(100)`不会影响`list2`，因为`list2`和`list1`是两个独立对象，不共享内存地址。`list1[0].append(3)`导致`list1`和`list2`的第一个列表元素同时增加元素3，因为它们引用同一个列表。而`list1[1] += (50, 60)`则在`list1`中创建新元组，并不影响`list2`，因为`list2`未引用新元组。
set()函数用于创建无序且不重复元素的集合。可以进行交集、并集和差集的运算。
例如，定义`x = set('eleven')`和`y = set('twelve')`后，可以通过`&`、`|`、`-`和`^`运算符计算交集、并集、差集和补集。
列表的常见方法：
1. `append()`：将一个元素添加到列表末尾。
2. `clear()`：清空列表内容。
3. ``：常规赋值实现浅拷贝，而`deep()`函数用于深拷贝。
4. `count()`：计算列表中指定元素出现的次数。
5. `extend()`：允许将多个值添加到列表末尾，接收一个序列作为参数。
6. `index()`：查找指定值第一次出现的索引。
7. `insert()`：在指定位置插入一个对象到列表中。
8. `pop()`：移除并返回列表末尾元素，`pop(index)`用于移除指定位置的元素。
9. `remove()`：删除列表中第一个与指定值匹配的元素。
10. `reverse()`：反转列表元素的顺序。
11. `sort()`：对列表进行排序。
高级排序使用`sort()`函数的`key`参数设置排序依据，`reverse`参数决定排序方向。
二叉树深度遍历算法通常用于遍历树结构的每个节点。常见的遍历类型包括前序遍历、中序遍历和后序遍历。
遍历算法可以应用于二叉树的遍历，例如获取所有从根节点到叶子节点的元素列表集合，可以使用深度优先搜索（DFS）来实现，具体步骤包括遍历左右子树和处理当前节点。
㈢ python的os.walk()为什么那么强悍
Python的os.walk()之所以强大，关键在于它巧妙地使用了递归和生成器技术。os.walk()函数遍历指定目录下的所有子目录与文件，其代码设计简洁高效，能够处理复杂的文件结构。
递归是os.walk()实现深度遍历的核心机制。通过调用自身，os.walk()可以逐级访问目录及其子目录，确保所有文件和子目录都被扫描。这种方式避免了复杂的循环嵌套，使得代码更加优雅且易于理解和维护。
生成器则是os.walk()的另一大亮点。生成器是一种特殊的迭代器，它允许函数在需要时生成结果，而不是一次性计算并存储所有结果。os.walk()通过yield语句生成目录、文件及其路径，用户可以在遍历过程中处理每个元素，无需一次性加载大量数据到内存中。这种设计极大地节省了内存资源，尤其在处理大量文件时更为关键。
此外，os.walk()还提供了灵活性选项，如topdown参数控制遍历顺序，onterror处理错误，followlinks处理符号链接等。这些功能使得os.walk()能够适应各种复杂场景，满足不同需求。
综上所述，os.walk()的强大之处在于其高效、灵活和内存友好的设计。通过递归和生成器技术，它能够在复杂的文件系统中轻松地遍历目录和文件，且具备高度的可扩展性和适应性。因此，os.walk()成为了Python中处理文件系统操作的首选工具。
㈣ python遍历列表
在Python中遍历列表是一项基本的操作。下面将介绍如何使用不同的方法遍历列表。
1. 使用简单的for循环结构遍历
你可以直接使用for循环来遍历列表，例如：
```python
for item in my_list:
print(item)
```
这将打印出列表`my_list`中的每个元素。
2. 运用`range()`和`len()`函数遍历
如果你需要同时获取元素和它的索引，可以使用`range()`和`len()`函数，例如：
```python
for i in range(len(my_list)):
print(i, my_list[i])
```
这将打印出列表`my_list`中每个元素的索引和值。
3. 运用`enumerate()`函数遍历
`enumerate()`函数提供了另一种遍历列表的方法，它自动返回元素和它们的索引，例如：
```python
for i, item in enumerate(my_list):
print(i, item)
```
这同样会打印出列表`my_list`中每个元素的索引和值。
以上就是在Python中遍历列表的三种常见方法。选择哪一种方法取决于你的具体需求，每种方法都有其适用的场景。希望这些信息能够帮助你更好地理解和使用Python中的列表遍历。
㈤ python：38.二叉树深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
2. 非递归
采用层次遍历的方法，访问每一层。首先构造一个数列，将每一层结点放进去列表中之后再取出，每取出一次计数加1，当列表为空时，计数结束返回count.
使用队列实现层次遍历，从根节点开始，将根节点入队。然后开始循环，每次出队一个节点，将该节点的左右子节点入队（如果存在）。这个过程一直循环到队列为空，此时队列内节点均已遍历，计数即为树的深度。
非递归方法的优势在于不需要额外的递归调用栈空间，适合处理树的深度较大的情况。通过不断遍历队列，可以确保每层的节点都得到访问，从而准确计算出树的深度。
总结，二叉树深度计算有递归和非递归两种方法。非递归方法采用层次遍历，使用队列结构，通过计数每次队列为空时的次数来确定树的深度。这种方法空间效率较高，适用于树结构深度较大的情况。