Python面试30分钟突击掌握-LeetCode4-Tree

如果你正在准备 Python 开发岗面试树Tree是绕不开的高频考点。和数组、链表不同树是非线性结构所以很多同学一上来会“脑子里没有图”。这一篇继续沿用前几篇的突击方式只抓最常考、最能代表树题思维的经典题先把基础分拿稳。为什么 Tree 在面试里总出现面试官偏爱树题核心是它能同时考你三件事递归思维是否清晰子问题定义是否准确边界条件是否稳空节点、叶子节点、范围约束是否真正理解 DFS / BFS 各自适用场景。如果你只有 30 分钟建议优先吃透这两题Maximum Depth of Binary TreeValidate Binary Search Tree这两题分别训练递归深度计算树形 DFS 基础带上下界约束的递归校验BST 核心今天的突击目标先做到下面四点不求多但求稳能独立写出最大深度的 DFS 解法能解释为什么“只比较父子节点”不足以验证 BST复杂度分析可以脱口而出能主动讲出空树、极值、重复值等边界情况。题目一Maximum Depth of Binary Tree二叉树的最大深度题目描述给定二叉树根节点root返回它的最大深度。最大深度指从根节点到最远叶子节点的最长路径上的节点数。示例输入[3,9,20,null,null,15,7]输出3输入[1,null,2]输出2面试中的思考路径这是树题的入门模板空节点深度是0非空节点深度是1 max(左子树深度, 右子树深度)。你会发现这就是“先定义子问题再组合答案”的标准递归写法。Python 参考实现DFS 递归fromtypingimportOptionalclassSolution:defmaxDepth(self,root:Optional[TreeNode])-int:ifrootisNone:return0return1max(self.maxDepth(root.left),self.maxDepth(root.right))复杂度分析时间复杂度O(n)每个节点访问一次空间复杂度O(h)h是树高递归栈深度。面试易错点把空节点深度写成1导致整体偏大只算左子树或右子树漏掉max说不清O(h)和O(n)的区别平衡树与退化树场景。题目二Validate Binary Search Tree验证二叉搜索树题目描述给定一个二叉树根节点root判断它是否是合法的二叉搜索树BST。BST 定义左子树所有节点值都严格小于当前节点右子树所有节点值都严格大于当前节点左右子树也必须分别是 BST。示例输入[2,1,3]输出true输入[5,1,4,null,null,3,6]输出false常见错误思路必须避坑很多人会写成“只比较当前节点和左右孩子”例如root.left.val root.valroot.right.val root.val这并不充分。因为 BST 约束是“整棵子树范围约束”不是“局部父子约束”。典型反例[5,1,6,null,null,4,7]节点4在根节点5的右子树里却小于5整棵树非法。正确思路递归传递上下界递归校验每个节点时同时携带可取值范围(low, high)当前节点值必须满足low node.val high递归左子树时上界变为当前节点值递归右子树时下界变为当前节点值。Python 参考实现fromtypingimportOptionalclassSolution:defisValidBST(self,root:Optional[TreeNode])-bool:defdfs(node:Optional[TreeNode],low:float,high:float)-bool:ifnodeisNone:returnTrueifnot(lownode.valhigh):returnFalsereturndfs(node.left,low,node.val)anddfs(node.right,node.val,high)returndfs(root,float(-inf),float(inf))复杂度分析时间复杂度O(n)每个节点访问一次空间复杂度O(h)递归栈深度。面试易错点把判断写成/导致重复值误判只做父子比较漏掉全局范围约束上下界更新写反左子树应更新上界右子树应更新下界。30 分钟高效练习法Tree 版按这个节奏走效率最高5 分钟先画树口述两题递归定义10 分钟手写maxDepth重点练递归基线10 分钟手写isValidBST重点练上下界传递5 分钟脱稿复述复杂度、边界和常见错误。树题最重要的是“递归含义明确”不是“代码背下来”。面试表达模板可直接套用你可以这样说树题我会先定义子问题再写递归返回值含义。对于校验类题目我会注意是局部约束还是全局约束必要时通过参数传递上下界。在复杂度上通常是线性遍历节点空间主要来自递归栈深度。写完后我会重点检查空树、单节点、重复值和极端不平衡树。这段话非常适合 Tree 题开场能让面试官快速看到你的解题框架。小结Tree 并不比链表“高深很多”关键是把递归框架和约束意识建立起来。把Maximum Depth of Binary Tree和Validate Binary Search Tree吃透后你会对二叉树题的主干套路更有把握。面试前请至少达到这个标准maxDepth一遍写对并能解释递归含义明确知道 BST 不能只做父子比较low/high范围递归写法熟练复杂度、边界、易错点都能讲清楚。下一篇可以继续练Sorting and Searching把“递归结构题 数组查找题”组合起来面试发挥会更稳定。支持一下如果这篇对你有帮助欢迎点赞、收藏、关注。 有余力的话欢迎打赏支持我会更新得更快。