免费企业网站建站,百度账号24小时人工电话,网络营销题库及答案2020,网页制作工程师目录
1. 啥时候用二叉树#xff1f;
#xff08;1#xff09;典型问题
#xff08;2#xff09;核心思路
2. BFS、DFS、BST
2.1 广度优先搜索BFS
#xff08;1#xff09;适用任务
#xff08;2#xff09;解决思路#xff1a;使用队列逐层遍历
2.2 深度…目录
1. 啥时候用二叉树
1典型问题
2核心思路
2. BFS、DFS、BST
2.1 广度优先搜索BFS
1适用任务
2解决思路使用队列逐层遍历
2.2 深度优先搜索DFS
1三种变体前中后序
2解决思路递归实现
2.3 二叉搜索树BST
3. LeetCode
3.1 BFS
1199 二叉树的右视图
21161 最大层内元素和
3.2 DFS
1104 二叉树的最大深度
2872 叶子相似的树
31448 统计二叉树中好节点的数目
41372 二叉树中的最长交错路径
5236 二叉树的最近公共祖先
3.3 BST
1700 二叉搜索树中的搜索
2450 删除二叉搜索树中的节点
398 验证二叉搜索树
4230 二叉搜索树中第k小的元素 1. 啥时候用二叉树
1典型问题 分层数据处理文件系统、组织架构 高效搜索BST中查找/插入/删除 路径问题根节点到叶节点的路径 树形结构操作镜像、深度、平衡性判断 表达式解析语法树 2核心思路
def solve(root):if root is None: # 关键始终先处理空节点return base_value # 如深度为0路径为空列表等# 递归分解子问题left_result solve(root.left) # 处理左子树right_result solve(root.right) # 处理右子树# 合并结果根据问题类型选择策略return combine(root.val, left_result, right_result)
2. BFS、DFS、BST
2.1 广度优先搜索BFS
1适用任务 -- 层序遍历按层级输出节点 -- 最短路径根节点到目标节点的最小深度 -- 寻找最近邻节点 2解决思路使用队列逐层遍历
from collections import dequedef bfs(root):if not root: return []queue deque([root])result []while queue:level []for _ in range(len(queue)): # 遍历当前层node queue.popleft()level.append(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)result.append(level) # 保存当前层结果return result
2.2 深度优先搜索DFS
1三种变体前中后序 遍历方式 应用场景 解决任务 操作顺序 前序遍历 节点初始化、路径记录、自顶向下操作 复制树、表达式前缀表示 根 → 左 → 右 中序遍历 二叉搜索树操作、顺序相关处理 BST升序输出、表达式解析 左 → 根 → 右 后序遍历 子树信息统计、依赖子树结果的操作 子树统计、内存释放 左 → 右 → 根
关键判断依据当前节点操作与子树操作的关系 如果操作依赖子树结果 → 用后序遍历如树深度、子树统计 如果操作在前子树操作前必须完成 → 用前序遍历如路径记录、节点初始化 如果涉及顺序处理 → 用中序遍历如BST中序遍历有序 2解决思路递归实现 前序遍历
def preorder(root):if not root: returnprint(root.val) # 先操作根节点preorder(root.left)preorder(root.right) 中序遍历 (BST关键)
def inorder(root):if not root: returninorder(root.left)print(root.val) # 在中间操作节点inorder(root.right) 后序遍历
def postorder(root):if not root: returnpostorder(root.left)postorder(root.right)print(root.val) # 最后操作根节点
2.3 二叉搜索树BST
左子树节点值 根节点值 右子树节点值
1典型任务 -- 查找元素时间复杂度 O(log n) -- 插入/删除节点保持BST性质 -- 范围查询如找出值在 [low, high] 间的节点 2代码模板 BST查找
def search(root, target):while root:if root.val target: return Trueroot root.left if target root.val else root.rightreturn False BST插入递归版
def insert(root, val):if not root: return TreeNode(val)if val root.val: root.left insert(root.left, val)elif val root.val: root.right insert(root.right, val)return root # 返回更新后的子树根节点 验证BST中序遍历应用
def isValidBST(root):stack, prev [], float(-inf)while stack or root:while root: # 深入左子树stack.append(root)root root.leftroot stack.pop()if root.val prev: return False # 破坏升序prev root.valroot root.right # 转向右子树return True
3. LeetCode
3.1 BFS
1199 二叉树的右视图
给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 本质上就是二叉树每一层的最后一个入队的节点 from collections import deque
class Solution(object):def rightSideView(self, root)::type root: Optional[TreeNode]:rtype: List[int]if not root: return []result[]quene deque([root])while quene:sizelen(quene)for i in range(size):node quene.popleft()if node.left: quene.append(node.left)if node.right:quene.append(node.right)cur_level_last node.valresult.append(cur_level_last)return result
21161 最大层内元素和
给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层而根节点的子节点位于第 2 层依此类推。请返回层内元素之和最大的那几层可能只有一层的层号并返回其中最小的那个。
from collections import deque
class Solution(object):def maxLevelSum(self, root)::type root: Optional[TreeNode]:rtype: intif not root: return 0quene deque([root])level1max_sum[root.val, level]while quene:level_sum 0level 1for i in range(len(quene)):node quene.popleft()level_sum node.valif node.left: quene.append(node.left)if node.right:quene.append(node.right)if max_sum[0]level_sum:max_sum [level_sum, level-1]return max_sum[1]
3.2 DFS
1104 二叉树的最大深度
给定一个二叉树 root 返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
DFS方法后序遍历先看左右子树的深度更深的1即为整棵树的最大深度。
class Solution(object):def maxDepth(self, root)::type root: Optional[TreeNode]:rtype: intif not root:return 0left_depth self.maxDepth(root.left)right_depth self.maxDepth(root.right)return max(left_depth,right_depth)1
BFS方法
from collections import deque
class Solution(object):def maxDepth(self, root)::type root: Optional[TreeNode]:rtype: intif not root:return 0quene deque([root]) ## 队列中存的是当前层的所有节点result [] ## 用来保存每一层的节点while quene:cur_level [] ## 当前层的节点level_size len(quene) ## 当前层有几个节点for i in range(level_size):node quene.popleft() cur_level.append(node.val) ## 将当前节点加入当前层中if node.left: quene.append(node.left)if node.right: quene.append(node.right)result.append(cur_level)return len(result)
2872 叶子相似的树
如果有两棵二叉树的叶值序列是相同那么我们就认为它们是 叶相似 的。如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的则返回 true否则返回 false 。 DFS遍历都是先左后右的因此均能保证叶子节点的顺序。 from collections import deque
class Solution(object):def find_leaves(self,root,leaves):if not root: return[]left_leaves self.find_leaves(root.left,leaves)if not root.left and not root.right:leaves.append(root.val)right_leaves self.find_leaves(root.right,leaves)return leavesdef leafSimilar(self, root1, root2)::type root1: Optional[TreeNode]:type root2: Optional[TreeNode]:rtype: boolleaves1[]leaves2[]leaves1 self.find_leaves(root1,leaves1)leaves2 self.find_leaves(root2,leaves2)if leaves1leaves2:return Trueelse:return False
31448 统计二叉树中好节点的数目
给你一棵根为 root 的二叉树请你返回二叉树中好节点的数目。「好节点」X 定义为从根到该节点 X 所经过的节点中没有任何节点的值大于 X 的值。 采用前序遍历根 → 左 → 右 根节点优先处理在访问子节点前先判断当前节点符合路径顺序 及时更新最大值当遇到更大节点时立即更新路径最大值传递给子节点 class Solution(object):def dfs(self,root,cur_max):if not root: return 0count 0if root.valcur_max:count1cur_max root.valcount self.dfs(root.left,cur_max)count self.dfs(root.right,cur_max)return countdef goodNodes(self, root)::type root: Optional[TreeNode]:rtype: intcur_max-10001return self.dfs(root,cur_max)
41372 二叉树中的最长交错路径
给你一棵以 root 为根的二叉树二叉树中的交错路径定义如下
选择二叉树中 任意 节点和一个方向左或者右。如果前进方向为右那么移动到当前节点的的右子节点否则移动到它的左子节点。改变前进方向左变右或者右变左。重复第二步和第三步直到你在树中无法继续移动。
交错路径的长度定义为访问过的节点数目 - 1单个节点的路径长度为 0 。请你返回给定树中最长 交错路径 的长度。 使用后序遍历①当前节点的状态计算依赖子节点状态 ②需要先知道子节点的 left_path 和 right_path 才能计算当前节点 class Solution(object):def longestZigZag(self, root)::type root: Optional[TreeNode]:rtype: int self.max_path 0def dfs(node):后序遍历返回(left_path, right_path)left_path: 从当前节点出发第一步向左走能形成的最长交错路径长度right_path: 从当前节点出发第一步向右走能形成的最长交错路径长度if not node:return (0, 0)left_res dfs(node.left) right_res dfs(node.right)从当前节点向左走一步到左子节点1然后需要向右走查询左子节点的向右走状态(right_path即left_res[1])left_path 1 left_res[1] if node.left else 0 从当前节点向右走一步到右子节点1然后需要向左走查询右子节点向左走的状态(left_path即right_res[0])right_path 1 right_res[0] if node.right else 0self.max_path max(self.max_path, left_path, right_path)return (left_path, right_path)dfs(root)return self.max_path
5236 二叉树的最近公共祖先 祖先可能的情况 1p 和 q 分属不同子树 → 当前根节点是 LCA 2p 和 q 在同一子树 → LCA 在该子树中 3p 或 q 自身就是 LCA祖孙关系 → 采用后序遍历顺序左右根 先深入子树寻找节点再处理当前节点判断逻辑 class Solution(object):def lowestCommonAncestor(self, root, p, q)::type root: TreeNode:type p: TreeNode:type q: TreeNode:rtype: TreeNodeif not root or rootp or rootq:return rootleft self.lowestCommonAncestor(root.left,p,q) ## 在左子树中找到的p或q或LCAright self.lowestCommonAncestor(root.right,p,q) ## 在右子树中找到的p或q或LCAif left and right: ## p和q分别在root的左右子树中 return root ## root是它们最低层级的共同祖先if left: ## 两个节点必定都在左子树中## 此时left要么是p和q中的一个如果尚未找到两者关系要么是p和q的LCA如果已找到两者关系return left return right
3.3 BST
1700 二叉搜索树中的搜索
给定二叉搜索树BST的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在则返回 null 。
class Solution(object):def searchBST(self, root, val)::type root: Optional[TreeNode]:type val: int:rtype: Optional[TreeNode]if not root: return nullwhile root:if root.valval:return rootelif root.valval:rootroot.rightelse:rootroot.left
2450 删除二叉搜索树中的节点 要被删除的节点存在三种情况 1. 叶子节点直接删除返回None 2. 只有一个子节点用子节点替代当前节点 实现直接返回子节点是让父节点直接指向孙子节点 3. 有两个子节点找到前置节点当前节点左子树中最右侧节点替换 实现用前置节点值覆盖当前节点值 → 删除前置节点递归调用 class Solution(object):def deleteNode(self, root, key)::type root: Optional[TreeNode]:type key: int:rtype: Optional[TreeNode]if not root: return Noneif keyroot.val: ## key比当前节点大在右子树中删root.rightself.deleteNode(root.right,key)elif keyroot.val: ## key比当前节点小在左子树中删root.leftself.deleteNode(root.left,key)else: ## 找到要删的节点了有以下4种情况 1.当前节点是叶子节点 → 直接删除if not root.left and not root.right:return None 2.当前节点只有左孩子 → 直接用左孩子替代当前节点elif not root.right:return root.left 3.当前节点只有右孩子 → 直接用右孩子替代当前节点 elif not root.left:return root.right 4. 当前节点左右孩子都有 → 用左子树的最右侧节点替代 else:## 寻找前置节点pre root.left while pre.right:prepre.right## 前置节点值赋给当前节点root.val pre.val ## 删除原前置节点 root.left self.deleteNode(root.left,pre.val)return root
398 验证二叉搜索树 方案一递归实现 每个节点都有值范围约束lowhigh 左子树继承上界lownode.val右子树继承下界node.valhigh class Solution(object):def isValidBST(self, root)::type root: Optional[TreeNode]:rtype: booldef validate(node, lowfloat(-inf), highfloat(inf)):if not node:return Trueif node.vallow or node.valhigh:return Falseis_left validate(node.left, low, node.val)is_right validate(node.right, node.val, high)return is_left and is_rightreturn validate(root) 方案二中序遍历验证 使用栈模拟中序遍历过程比较当前节点与前一个节点的值 class Solution(object):def isValidBST(self, root):stack[]preNonewhile stack or root: 左 while root: stack.append(root)rootroot.left 根 rootstack.pop()if pre is not None and root.valpre: return False ## 当前值比pre值其左侧小 右 preroot.valrootroot.rightreturn True
4230 二叉搜索树中第k小的元素 因为搜索树的中序遍历得到一个递增序列所以本质上就是求中序遍历的第k个值。 class Solution(object):def kthSmallest(self, root, k)::type root: Optional[TreeNode]:type k: int:rtype: intstack[]count0while root or stack:## 左while root:stack.append(root)rootroot.left## 根rootstack.pop()count1if countk: ## 是否是第k个 return root.val## 右rootroot.right
