算法工程师面试必考项:二叉树
机器学习算法工程师
共 11612字,需浏览 24分钟
·
2020-08-24 21:24
AI作者:田旭
AI编辑:田旭
1 二叉树简介
二叉树是最基本的数据结构之一,二叉树(Binary Tree)是包含n个节点的有限集合,该集合或者为空集(此时,二叉树称为空树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
一个典型的二叉树如下图所示
在二叉树中,第
层上至多有 个节点 深度为的二叉树至多有
个节点 对一棵二叉树,如果叶子节点的个数为
,度为2的节点个数为 ,则 具有
个节点的完全二叉树的深度为⌊⌋+1
2 二叉树的遍历
以根访问顺序决定是什么遍历 左子树都是优先右子树
2.1 递归解法
2.1.1 前序遍历
def preorderTraversal(self, root: TreeNode) -> List[int]:
def dfs(root):
if not root:
return
res.append(root.val) # 将根节点插入栈中
dfs(root.left)
dfs(root.right)
dfs(root)
return res
2.1.2 中序遍历
def inorderTraversal(self, root: TreeNode) -> List[int]:
def dfs(root):
if not root:
return
dfs(root.left)
res.append(root.val) # 将根节点插入栈中
dfs(root.right)
dfs(root)
return res
2.1.3 后序遍历
def posorderTraversal(self, root: TreeNode) -> List[int]:
def dfs(root):
if not root:
return
dfs(root.left)
dfs(root.right)
res.append(root.val) # 将根节点插入栈中
dfs(root)
return res
2.2 迭代解法
2.2.1 前序遍历
# 常规解法
def preorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return []
res = []
stack = [root] # 辅助栈
while stack:
root = stack.pop()
if root is not None:
res.append(root.val)
if root.right is not None:
stack.append(root.right)
if root.left is not None:
stack.append(root.left)
return res
# 模版解法
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [] # 辅助栈
while stack or root:
while root:
'''
这其实就是在对于每个节点,遍历它的左孩子链,并且在遍历的过程中,保存遍历的结果,并且在每遍历一个左节点的时候,都添加它的右孩子到辅助栈中
'''
res.append(root.val) # 将根节点加入列表
stack.append(root)
root = root.left # 遍历左子树
root = stack.pop() # 左子树遍历完毕
root = root.right # 遍历右子树
return res
# 颜色标记法
'''
使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色,则将节点的值输出。
令白色为0,灰色为1
'''
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [(0, root)]
while stack:
flag, node = stack.pop()
if node is None: continue # 空结点跳过
if flag == 0:
# 前序的倒序记录,子结点标记为 1,已经标过 1 的父结点状态置为 0
stack.append((0, node.right))
stack.append((0, node.left))
stack.append((1, node))
else: # 标记为1则输出
res.append(node.val)
return res
2.2.2 中序遍历
# 模版解法
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [] # 辅助栈
while stack or root:
while root:
stack.append(root)
root = root.left # 遍历左子树
root = stack.pop() # 左子树遍历完毕
res.append(root.val) # 将根节点加入列表
root = root.right # 遍历右子树
return res
# 颜色标记法
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [(0, root)]
while stack:
flag, node = stack.pop()
if node is None: continue # 空结点跳过
if flag == 0:
# 前序的中序记录,子结点标记为 1,已经标过 1 的父结点状态置为 0
stack.append((0, node.right))
stack.append((1, node))
stack.append((0, node.left))
else: # 标记为1则输出
res.append(node.val)
return res
2.2.3 后序遍历
# 模版解法
# 将前序遍历结果倒叙输出
def posorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [] # 辅助栈
while stack or root:
while root:
res.append(root.val) # 将根节点加入列表
stack.append(root)
root = root.left # 遍历左子树
root = stack.pop() # 左子树遍历完毕
root = root.right # 遍历右子树
return res[::-1]
# 颜色标记法
def preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
stack = [(0, root)]
while stack:
flag, node = stack.pop()
if node is None: continue # 空结点跳过
if flag == 0:
# 后序的中序记录,子结点标记为 1,已经标过 1 的父结点状态置为 0
stack.append((0, node))
stack.append((0, node.left))
stack.append((1, node.right))
else: # 标记为1则输出
res.append(node.val)
return res
2.3 层序遍历
初始化队列 q,并将根节点 root 加入到队列中; 当队列不为空时: 队列中弹出节点 node,加入到结果中; 如果左子树非空,左子树加入队列; 如果右子树非空,右子树加入队列;
# BFS
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
queue = [root]
while queue:
level = [] # 保存每一层的节点
for _ in range(len(queue)):
node = queue.pop(0) # 取队列头节点
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level)
return res
# DFS 使用递归调用DFS,添加一个深度的参数
# 记录每个节点的深度 depth。递归到新节点要把该节点放入 depth 对应列表的末尾
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if not root:
return
def dfs(node, depth):
if len(res) == depth:
res.append([]) # 当一层遍历完,添加[]
res[depth].append(node.val) # 将节点添加进[]末尾
if node.left is not None:
dfs(node.left, depth + 1)
if node.right:
dfs(node.right, depth + 1)
dfs(root, 0)
return res
给定一个二叉树,返回其节点值自底向上的层次遍历。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
# BFS
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
res = []
queue = [root]
while queue:
level = [] # 保存每一层的节点
for _ in range(len(queue)):
node = queue.pop(0) # 取队列头节点
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.insert(0, level) # 插入到列表开头
return res
# DFS 使用递归调用DFS,改用insert插入到列表开头
def levelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if not root:
return
def dfs(node, depth):
if len(res) == depth:
res.insert(0, []) # 当一层遍历完,插入[]到开头
res[-(depth+1)].append(node.val) # 将节点添加进[]
if node.left is not None:
dfs(node.left, depth + 1)
if node.right:
dfs(node.right, depth + 1)
dfs(root, 0)
return res
3 常见题目示例
104. 二叉树的最大深度
给定一个二叉树,找出其最大深度。
# BFS
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
queue = [(1, root)] # 添加一个层数depth参数
while queue:
depth, root = queue.pop(0)
if root.left:
queue.append((depth+1, root.left))
if root.right:
queue.append((depth+1, root.right))
return depth
# 分治算法
def maxDepth(self, root: TreeNode) -> int:
if root is None:
return 0
left = self.maxDepth(root.left)
right = self.maxDepth(root.right)
if left > right:
return left + 1
else:
return right + 1
110. 平衡二叉树
给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
# 分治法
def isBalanced(self, root: TreeNode) -> bool:
def maxDepth(root):
if not root:
return 0
left = maxDepth(root.left)
if left == -1:
return -1
right = maxDepth(root.right)
if right == -1:
return -1
return max(left, right) + 1 if abs(left - right) < 2 else -1
return maxDepth(root) != -1
def isBalanced(self, root: TreeNode) -> bool:
def maxDepth(root):
if not root:
return True, 0
lf, lh = maxDepth(root.left)
rf, rh = maxDepth(root.right)
if lf and rf and abs(lh-rh) < 2:
return True, max(lh, rh) + 1
return False, max(lh, rh) + 1
return maxDepth(root)[0]
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
当 left 和 right 同时为空 :说明 root 的左 / 右子树中都不包含 p,q ,返回 None ; 当 left 和 right 同时不为空 :说明 p, q 分列在 root 的 异侧 (分别在 左 / 右子树),因此 root 为最近公共祖先,返回 root ; 当 left 为空 ,right 不为空 :p, q都不在 root 的左子树中,直接返回 right 。具体可分为两种情况:
当 left 不为空 , right 为空 :与情况 3. 同理;
# 左搜搜,右搜搜。左右都有,那就是你;左没便在右,右没便在左
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root in (None, p, q): # 如果不为树,或者p或q为根节点,则直接返回根节点
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: # 左右节子树返回值均不为None
return root
if not left: # 左没便在右
return right
if not right: # 右没便在左
return left
103. 二叉树的锯齿形层次遍历
给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
def helper(root, depth):
if not root:
return
if len(res) == depth:
res.append([])
if depth %2 == 0: # 偶数行正常排序
res[depth].append(root.val)
else: # 奇数行倒序插入
res[depth].insert(0, root.val)
helper(root.left, depth + 1)
helper(root.right, depth + 1)
helper(root, 0)
return res
701. 二叉搜索树中的插入操作
给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。返回插入后二叉搜索树的根节点。保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。
# DFS递归查找插入位置
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
if not root: # 根节点为空,则直接插入到根节点的位置
return TreeNode(val)
# 当root.val > val时,插入到左子树
if root.val > val:
root.left = self.insertIntoBST(root.left, val)
# 当root.val < val时,插入到右子树
else:
root.right = self.insertIntoBST(root.right, val)
return root
# 迭代
def insertIntoBST(self, root: TreeNode, val: int) -> TreeNode:
node = root # 创建指针指向root
while node:
# 当node.val > val时,插入到左子树
if node.val > val:
if not node.left: # 当左子树没有左子节点,则插入到左子树左子节点
node.left = TreeNode(val)
return root
else: # 左子节点存在,则指针指向左子节点
node = node.left
else:
if not node.right:
node.right = TreeNode(val)
return root
else: # 右子节点存在,则指针指向右子节点
node = node.right
return TreeNode(val)
98. 验证二叉搜索树
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
def isValidBST(self, root: TreeNode) -> bool:
# 中序遍历
stack = []
temp = float('-inf')
while stack or root:
while root:
stack.append(root)
root = root.left # 遍历左子树
root = stack.pop() # 左子树遍历完成,此时root为左子树叶子节点
# 由于节点遍历顺序是左根右,每次让当前节点与上一个保存当节点值比较,即当前为根节点,则上一个节点为左节点,值当前节点小于上一个节点,则返回False
if root.val <= temp:
return False
temp = root.val # temp值变为当前节点当值
root = root.right # 遍历右子树
return True
# 分治法
def isValidBST(self, root: TreeNode) -> bool:
def helper(root, lower = float('-inf'), upper = float('inf')):
# 递归终止条件,当递归到叶子节点,则退出
if not root:
return True
# 判断是否在区间内,即判断左 MAX < 根 < 右 MIN
if root.val <= lower or root.val >= upper:
return False
# 判断左子树,上边界设为根节点的值
if not helper(root.left, lower, root.val):
return False
# 判断右子树,下边界设为根节点的值
if not helper(root.right, root.val, upper):
return False
# 前面判断都没有返回False的情况,则是平衡树
return True
return helper(root)
124. 二叉树中的最大路径和
给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
def maxPathSum(self, root: TreeNode) -> int:
self.maxSum = float("-inf") # 定义全局变量,保存最大和
def maxGain(node):
if not node:
return 0
# 递归计算左右子节点的最大路径和
left = maxGain(node.left)
right = maxGain(node.right)
# 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大路径和
total = max(node.val,
node.val + left,
node.val + right)
# 更新最大路径和
self.maxSum = max(self.maxSum, total, node.val + left + right)
# 返回节点的最大贡献值
return total
maxGain(root)
return self.maxSum
Reference
[2] LeetCode 题解.
评论