二叉树
树
树是由n个结点组成的有限集合。
二叉树
二叉树不是树的特例，而是另一种不同的数据结构。
不同的二叉树
- 满二叉树
指的是每一层结点数都达到最大的二叉树，有k层，则有2^k-1个结点。 - 完全二叉树
要求比满二叉树低一些。
比起满二叉树，在最下一层最右侧可以允许少一些结点。
满二叉树一定是完全二叉树。
二叉树的存储结构
- 链式存储——链表存储
- 顺序存储——适合完全二叉树，否则容易造成内存空间浪费。
遍历
- 深度优先——前中后序
- 广度优先——层序遍历
高度和深度
高度和深度都是针对节点的概念。
- 深度指的是该节点到根节点最长简单路径的条数。
- 高度指的是该节点到叶子节点最长简单路径的条数。
根节点的高度就是二叉树的最大深度。
回溯
- 显式回溯
每一个递归对应一个回溯。要在同一个花括号里。
if cur.left: # 左self.traversal(cur.left, path, result)path.pop() # 回溯# leetcode 257二叉树的所有路径
- 隐式回溯
用path[:]传递变量可以传递一个副本，并不修改原path，则实现同样的效果。
if cur.left:self.traversal(cur.left, path[:], result)
python
定义
def __init__(self,val,left=None,right=None):self.val=valself.left=leftself.right=right
N叉树
for child in node.children:
遍历
for i,j in zip(range(),range()):
绝对值
abs()
易错点
栈
将结点加入stack之前（stack=[root]），注意检验root是否为None。
队列
- 用deque双向队列模拟单向队列
queue = collections.deque([root])
- 模拟时注意popleft()和pop()不要写混淆了
cur=queue.popleft()
- 用完pop要记得len改变了，别搞错了。或者就一开始把len赋一个变量。确定自己需要用的len是哪一个时刻的len。
除法/
除数为零会返回异常，一般需要做条件判断。
正负无穷
float(‘inf’)
float(‘-inf’)
用到max的时候经常需要用到无穷做初始化
对比节点的值
对比节点的值时记得写.val。
stack
在stack.append时，必须添加int，不能添加节点
求路径时，可以用.copy或list()添加。不能直接添加。
- 路径总和 II
stack.append(root.val)
#or
stack=[root.val]self.res.append(stack.copy())
#or
self.res.append(list(stack))
