做采集网站难不,网站外链有多重要,注册安全工程师考哪四门,做固定背景网站前言
元宵节快乐 ~ 周六在图书馆快乐刷题#xff01;继续二叉树#x1f374;
543. 二叉树的直径 - 力扣#xff08;LeetCode#xff09; 递归后序 class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int:self.res 0 # 记录最长路径# 递归…前言
元宵节快乐 ~ 周六在图书馆快乐刷题继续二叉树
543. 二叉树的直径 - 力扣LeetCode 递归后序 class Solution:def diameterOfBinaryTree(self, root: Optional[TreeNode]) - int:self.res 0 # 记录最长路径# 递归求最大深度def depth(node):if not node:return 0l depth(node.left) # 左子树最大深度r depth(node.right) # 右子树最大深度self.res max(self.res, l r) # 两边深度相加就是最长路径return max(l, r) 1 # 返回当前最大深度depth(root)return self.res
108. 将有序数组转换为二叉搜索树 - 力扣LeetCode 递归前序 class Solution:def sortedArrayToBST(self, nums: List[int]) - Optional[TreeNode]:def helper(left, right):if left right: return # left right也可以返回一个结点mid (left right) // 2root TreeNode(nums[mid]) # 构造根节点root.left helper(left, mid-1) # 比根节点小的为左子树root.right helper(mid1, right) # 比根节点大的为右子树return rootreturn helper(0, len(nums)-1) 98. 验证二叉搜索树 - 力扣LeetCode 递归BST 容易忽略上下界问题详看题解 class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:# 递归判断当前结点的值是否在上下界内def helper(node, minVal, maxVal):if not node:return True# 每个节点如果超过这个范围直接返回falseif node.val maxVal or node.val minVal:return False# 左子树范围的最小值是minVal最大值是当前节点的值因为左子树的值要比当前节点小l helper(node.left, minVal, node.val)# 右子树范围的最大值是maxVal最小值是当前节点的值因为右子树的值要比当前节点大r helper(node.right, node.val, maxVal)return l and r# 初始上下界无限大python用浮点数表示整数最大最小return helper(root, -float(inf), float(inf)) 递归中序 class Solution:# def __init__(self):# self.pre None # 公共变量def isValidBST(self, root: Optional[TreeNode]) - bool:self.pre None # 私有变量记录上一个结点def helper(root):if not root: return Truel helper(root.left) # 左if self.pre and self.pre.val root.val:return False # 中self.pre rootr helper(root.right) # 右return l and rreturn helper(root) 迭代中序 class Solution:def isValidBST(self, root: Optional[TreeNode]) - bool:if not root:return Truest []pre -float(inf)while st or root:while root:st.append(root)root root.lefttemp st.pop()if temp.val pre:return Falsepre temp.valroot temp.rightreturn True
230. 二叉搜索树中第K小的元素 - 力扣LeetCode 迭代中序 class Solution:def kthSmallest(self, root: Optional[TreeNode], k: int) - int:st []while st or root:while root:st.append(root)root root.lefttemp st.pop()k - 1if k 0: return temp.val # 遍历到第k个结点root temp.right 优化查找 # 扩展TreeNode
class TreeNode:def __init__(self, val0, leftNone, rightNone):self.val valself.left leftself.right rightself.node_num 0 # 以该结点为根结点的子树的结点数# 构造可供查找的MyBst类
class MyBst:def __init__(self, root: TreeNode):self.root rootself._count_node_num(root) # 初始化时计算每个结点为根结点的子树的结点数def kth_smallest(self, k: int):node self.rootwhile node:left node.left.node_num if node.left else 0 # 获取左子树的结点数if left k - 1:node node.right # 移动到右子树查找k - left 1 # 更新 k 值elif left k - 1:return node.val # 当前结点即为第 k 小的结点else:node node.left # 移动到左子树查找def _count_node_num(self, node) - int:if not node:return 0# 递归计算以当前结点为根结点的子树的结点数node.node_num 1 self._count_node_num(node.left) self._count_node_num(node.right)return node.node_num # 返回以当前结点为根结点的子树的结点数class Solution:def kthSmallest(self, root: TreeNode, k: int) - int:bst MyBst(root)return bst.kth_smallest(k) # 调用 MyBst 类的方法来找出第 k 小的结点的值
199. 二叉树的右视图 - 力扣LeetCode 迭代层序BFS class Solution:def rightSideView(self, root: Optional[TreeNode]) - List[int]:if not root: return []res []q deque()q.append(root)while q:n len(q) # 先存长度以防变化for i in range(n):cur q.popleft()if cur.left: q.append(cur.left)if cur.right: q.append(cur.right)if i n - 1: # 本层最后一个结点res.append(cur.val)return res 递归逆先序DFS # 思路类似【层序遍历】的 DFS递归
class Solution:def rightSideView(self, root: Optional[TreeNode]) - List[int]:self.res []# 传入层当前深度def dfs(root, depth):if not root: returnif depth len(self.res):self.res.append(root.val) # 中dfs(root.right, depth 1) # 右dfs(root.left, depth 1) # 左dfs(root, 0)return self.res
后言 刷简单的二叉树题就是爽递归的代码简短可以一次AC还有精力去理解别的解法多亏了之前刷代码随想录打的基础感觉多刷一两次就可以看到就写出来了刷二叉树信心MAX
