代码随想录算法训练营 Day 11
Published:
二叉树
常用的二叉树
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。若一棵满二叉树深度为k，那么其节点数量为$2^k - 1$
完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若一棵完全二叉树的的最底层为第k层，那么该层节点数量范围[1, $2^{(h-1)}$]
二叉搜素树（有序树）：1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；2.若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；3. 它的左、右子树也分别为二叉排序树
平衡二叉搜索树：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
存储方式
链式存储 - 用指针指向孩子节点
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
顺序存储 - 用数组存储；假如一个节点的索引为i，那么其左孩子节点的索引为$i * 2 + 1$，右孩子节点的索引为$i * 2 + 2$
遍历方式
深度优先遍历（DFS） - 递归法，迭代法
前序遍历：父节点 -> 左孩子节点 -> 右孩子节点 中序遍历：左孩子节点 -> 父节点 -> 右孩子节点 后序遍历：左孩子节点 -> 右孩子节点 -> 父节点
注意：左右孩子节点可能为一棵子树，需要再按照同样的顺序进行考虑
广度优先遍历（BFS） - 迭代法
递归遍历
递归三要素：1. 确定递归函数的参数和返回值；2. 确定终止条件；3. 确定单层递归的逻辑
前序遍历
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if not node:
return
res.append(node.val)
dfs(node.left)
dfs(node.right)
dfs(root)
return res
中序遍历
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if not node:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res
后序遍历
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
res = []
def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
res.append(node.val)
dfs(root)
return res
Take some notes
递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中
迭代遍历
利用栈将节点存储起来，然后每次从栈中推出节点
前序遍历
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
curr = stack.pop()
res.append(curr.val)
# 栈是先进后出，因此需要先将右节点放入栈中。这样先出栈的就是左节点
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
return res
中序遍历 (不能先将根节点放入栈中)
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
res = []
stack = []
curr = root
while curr or stack:
if curr:
stack.append(curr)
# 遍历左子树，直到不包含左子树
curr = curr.left
else:
curr = stack.pop()
res.append(curr.val)
# 取栈顶节点的右子树
curr = curr.right
return res
后序遍历
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
res = []
# 先按照中右左的顺序进行遍历，最后将结果翻转
while stack:
curr = stack.pop()
res.append(curr.val)
if curr.left:
stack.append(curr.left)
if curr.right:
stack.append(curr.right)
return res[::-1]
统一遍历
利用标记法，确定节点是否可以被加入到结果中
class Solution:
def Traversal(self, root: Optional[TreeNode]) -> List[int]:
if not root:
return []
stack = [root]
res = []
while stack:
curr = stack.pop()
if curr:
# 前序遍历
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
stack.append(curr)
stack.append(None)
# 中序遍历
if curr.right:
stack.append(curr.right)
stack.append(curr)
stack.append(None)
if curr.left:
stack.append(curr.left)
# 后序遍历
stack.append(curr)
stack.append(None)
if curr.right:
stack.append(curr.right)
if curr.left:
stack.append(curr.left)
else:
curr = stack.pop()
res.append(curr.val)
return res
Take some notes
注意使用栈进行迭代遍历时，入栈的顺序和遍历顺序的关系
层序遍历
Q1. LeetCode 102
解法1
from collections import deque
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if not root:
return res
queue = deque([root])
while queue:
temp = []
temp_q = []
for _ in range(len(queue)):
curr = queue.popleft()
temp.append(curr.val)
if curr.left:
temp_q.append(curr.left)
if curr.right:
temp_q.append(curr.right)
res.append(temp)
queue = deque(temp_q)
return res
解法2: 递归法
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
res = []
if not root:
return res
def bfs(node, l):
if not node:
return
if len(res) == l:
res.append([])
res[l].append(node.val)
bfs(node.left, l + 1)
bfs(node.right, l + 1)
bfs(root, 0)
return res
Q2. LeetCode 107
将Q1结果进行翻转即可
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
res = []
queue = deque([root])
while queue:
temp = []
for _ in range(len(queue)):
curr = queue.popleft()
temp.append(curr.val)
if curr.left:
queue.append(curr.left)
if curr.right:
queue.append(curr.right)
res.append(temp)
return res[::-1]
Q3. LeetCode 199
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
res = []
if not root:
return res
queue = deque([root])
while queue:
for _ in range(len(queue) - 1):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
node = queue.popleft()
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return res
TODO
层序遍历的其他问题