二叉树的理论基础
二叉树的主要形式：
二叉树有两种主要的形式：满二叉树和完全二叉树；
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。可以说深度为k，有2^k-1个节点的二叉树。
完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。（有左子树可以，没有左子树，光有右子树的不是完全二叉树）
二叉搜索树：二叉搜索树是一个有序树；
* 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
* 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
* 它的左、右子树也分别为二叉排序树；
平衡二叉树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树的存储方式：
二叉树可以链式存储，也可以顺序存储。（链式存储方式就用指针， 顺序存储的方式就是用数组）
链式存储：通过节点元素的左指针和右指针分别对应左子树和右子树）
顺序存储：如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
二叉树的遍历方式
二叉树主要有2种遍历方式：深度优先遍历和广度优先遍历；
1、深度优先遍历
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
这里前中后，其实指的就是中间节点的遍历顺序，只要大家记住 前中后序指的就是中间节点的位置就可以了。
2、广度优先遍历
层次遍历（迭代法）
二叉树的定义
class TreeNode:
def __init__(self, val, left = None, right = None):
self.val = val
self.left = left
self.right = right二叉树的递归遍历
递归：每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
1、确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2、确定终止条件： 写完了递归算法,运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3、确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
144. 二叉树的前序遍历 - 力扣（LeetCode）
前序：先遍历节点，在左子树，在右子树先遍历节点，在左子树，在右子树
from typing import List
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def dfs(node):
if node is None:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res
if __name__ == '__main__':
null = None
root = root = [1, null, 2, 3]
root = generate_tree(root)
print('前序遍历:')
res = Solution().preorderTraversal(root) # 9 3 15 20 7
print(res)145. 二叉树的后序遍历 - 力扣（LeetCode）
后序：先左子树，在右子树，最后节点；
from typing import List
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def dfs(node):
if node is None:
return
dfs(node.left)
dfs(node.right)
res.append(node.val)
dfs(root)
return res
if __name__ == '__main__':
null = None
root = root = [1, null, 2, 3]
root = generate_tree(root)
print('后序遍历:')
res = Solution().inorderTraversal(root)
print(res)
94. 二叉树的中序遍历 - 力扣（LeetCode）
中序：先左子树，在节点，最后在右子树；
from typing import List
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def dfs(node):
if node is None:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res
if __name__ == '__main__':
null = None
root = root = [1, null, 2, 3]
root = generate_tree(root)
print('中序遍历:')
res = Solution().postorderTraversal(root)
print(res)二叉树的迭代遍历
144. 二叉树的前序遍历 - 力扣（LeetCode）
前序遍历（迭代法）：前序遍历顺序是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈中（因为出栈的时候顺序才是中左右），再加入左孩子；
from typing import List
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
# 先将根节点的进行弹出；后续弹出2层节点（子树）
node = stack.pop()
# 弹出的值进行保存；
res.append(node.val)
# 先保存右子树
if node.right:
stack.append(node.right)
# 再保存左子树
if node.left:
stack.append(node.left)
return res
if __name__ == '__main__':
null = None
root = root = [1, null, 2, 3]
root = generate_tree(root)
print('前序遍历:')
res = Solution().preorderTraversal(root)
print(res)
145. 二叉树的后序遍历 - 力扣（LeetCode）
后序遍历可以从前序遍历中适当调整，将顺序改成（中右左）然后反向，就成了左右中的后序遍历，所以需要在前序中先处理根节点，在处理左孩子，最后右孩子；最后反向完成；
from typing import List
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
# 先将根节点的进行弹出；后续弹出2层节点（子树）
node = stack.pop()
# 弹出的值进行保存；
res.append(node.val)
# 先保存左子树
if node.left:
stack.append(node.left)
# 再保存右子树
if node.right:
stack.append(node.right)
return res[::-1]
if __name__ == '__main__':
null = None
root = root = [1, null, 2, 3]
root = generate_tree(root)
print('后序遍历:')
res = Solution().postorderTraversal(root)
print(res)
94. 二叉树的中序遍历 - 力扣（LeetCode）
中序遍历与前序和后序遍历不同，不能提前将根节点放入栈中，因为中序遍历顺序是左中右；
操作：
1、处理：将元素放入result数组中；
2、访问：遍历节点
在使用迭代法写中序遍历，就需要借助指针的遍历来帮忙访问节点，栈则用来处理节点上的元素；
from typing import List
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if not root:
return []
# 不能提前将root节点加入stack中
stack = []
res = []
cur = root
while cur or stack:
# 先访问左节点
if cur:
stack.append(cur)
cur = cur.left
# 再处理顶节点和右节点
else:
cur = stack.pop()
res.append(cur.val)
cur = cur.right
return res
if __name__ == '__main__':
null = None
root = root = [1, null, 2, 3]
root = generate_tree(root)
print('中序遍历:')
res = Solution().inorderTraversal(root)
print(res)
二叉树的统一迭代法
前序遍历：
class Solution:
# 前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
if root:
stack.append(root)
while stack:
node = stack.pop()
if node != None:
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
stack.append(node)
stack.append(None)
else:
node = stack.pop()
res.append(node.val)
return res中序遍历：
class Solution:
# 中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = []
if root:
stack.append(root)
while stack:
node = stack.pop()
if node != None:
if node.right: # 右
stack.append(node.right)
stack.append(node) # 中
stack.append(None)
if node.left: # 左
stack.append(node.left)
else:
node = stack.pop()
res.append(node.val)
return res后序遍历：
class Solution:
# 后序遍历
def postorderTraversal(self, root: TreeNode) -> List[int]:
result = []
stack = []
if root:
stack.append(root)
while stack:
node = stack.pop()
if node != None:
stack.append(node) # 中
stack.append(None)
if node.right: # 右
stack.append(node.right)
if node.left: # 左
stack.append(node.left)
else:
node = stack.pop()
result.append(node.val)
return result二叉树的层序遍历
层序遍历需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。（而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。）
102. 二叉树的层序遍历 - 力扣（LeetCode）
该题可以作为层序遍历的模板
from typing import List, Optional
from collections import deque
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = deque([root])
res = []
while queue:
level = []
# 根据层遍历
for _ in range(len(queue)):
cur = queue.popleft()
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
res.append(level)
return res
if __name__ == '__main__':
null = None
root = [3,9,20,null,null,15,7]
root = generate_tree(root)
res = Solution().levelOrder(root)
print(res)107. 二叉树的层序遍历 II - 力扣（LeetCode）
与LC102一样思路，就是把结果的数组进行反转就行
from typing import List, Optional
from collections import deque
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = deque([root])
res = []
while queue:
level = []
# 根据层遍历
for _ in range(len(queue)):
cur = queue.popleft()
level.append(cur.val)
if cur.left:
queue.append(cur.left)
if cur.right:
queue.append(cur.right)
res.append(level)
return res[::-1]
if __name__ == '__main__':
null = None
root = [3, 9, 20, null, null, 15, 7]
root = generate_tree(root)
res = Solution().levelOrderBottom(root)
print(res)199. 二叉树的右视图 - 力扣（LeetCode）
思路：层序遍历的时候，判断是否遍历到单层的最后面的元素，如果是，就放进result数组中，随后返回result就可以了。
from typing import List, Optional
from collections import deque
# 二叉树生成代码
def generate_tree(vals):
if len(vals) == 0:
return None
que = [] # 定义队列
fill_left = True # 由于无法通过是否为 None 来判断该节点的左子树是否可以填充，用一个记号判断是否需要填充左节点
for val in vals:
node = TreeNode(val) if val else None # 非空值返回节点类，否则返回 None
if len(que)==0:
root = node # 队列为空的话，用 root 记录根结点，用来返回
que.append(node)
elif fill_left:
que[0].left = node
fill_left = False # 填充过左子树后，改变记号状态
if node: # 非 None 值才进入队列
que.append(node)
else:
que[0].right = node
if node:
que.append(node)
que.pop(0) # 填充完右子树，弹出节点
fill_left = True #
return root
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
queue = deque([root])
# 右视图
right_view = []
while queue:
l = len(queue)
for i in range(l):
node = queue.popleft()
# 判断是否遍历到单层的最后面的元素
if i == l - 1:
right_view.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return right_view
if __name__ == '__main__':
null = None
root = [1,2,3,null,5,null,4]
root = generate_tree(root)
res = Solution().rightSideView(root)
print(res)层序遍历先写3题，其他的后序补充
标签：node,None,遍历,val,随想录,que,二叉树,root,left From： https://blog.csdn.net/weixin_49494409/article/details/144021096